Программа на Python для пузырьковой сортировки

В этой статье я объясню, как написать программу на Python для пузырьковой сортировки, используя различные методы, с некоторыми наглядными примерами.

• Что такое пузырьковая сортировка?
• Простой пример
• Методы и способы
• Метод 1: с использованием цикла for
• Метод 2: с использованием цикла while
• Метод 3: с использованием понимания списка
• Способ 1: с использованием функции
• Способ 2: без использования функции
• Способ 3: с пользовательским вводом

Что такое пузырьковая сортировка?

Пузырьковая сортировка — это простой алгоритм сортировки, который неоднократно проходит через список элементов Python, подлежащих сортировке, сравнивает соседние элементы и меняет их местами, если они расположены в неправильном порядке. Этот процесс повторяется до тех пор, пока не будет отсортирован весь список Python.

Простой пример

Давайте возьмем простой пример и поймем, что означает пузырьковая сортировка. Итак, здесь мы возьмем список Python, содержащий некоторое целочисленное значение:

Initial_List  = [25, 17, 7, 14, 6, 3]

Объяснение: Чтобы отсортировать список Python [25, 17, 7, 14, 6, 3], мы должны неоднократно сравнивать соседние элементы и менять их местами, если они расположены в неправильном порядке, пока не будет отсортирован весь список.

Вот как алгоритм пузырьковой сортировки будет работать шаг за шагом для нашего списка Python.

Проход 1:

После первого прохода самый большой элемент(25) был отсортирован пузырьком до конца списка Python.

Проход 2:

После второго прохода второй по величине элемент(17) переместился на предпоследнюю позицию в списке Python.

Проход 3:

После третьего прохода третий по величине элемент(14) переместился на предпоследнюю позицию в списке Python.

Проход 4:

После четвертого прохода четвертый по величине элемент(7) переместился на предпоследнюю позицию в списке Python.

Проход 5:

После пятого прохода пятый по величине элемент(6) переместился на предпоследнюю позицию в списке Python.

Проход 6:

Список в Python теперь полностью отсортирован, и никаких свопов больше не требуется.

Final Sorted List: [3, 6, 7, 14, 17, 25]

Список Python теперь сортируется по возрастанию с использованием алгоритма пузырьковой сортировки.

Я также создал изображение, чтобы вы лучше поняли весь этот процесс:

Как мы видим, на шестом проходе никакой замены не происходит, поэтому я не упомянул об этом на изображении.

Методы и способы

В Python существуют различные методы и способы, которые можно использовать для написания программы Python для пузырьковой сортировки.

Методы:

1. цикл for;
2. цикла while;
3. понимание списка

Пути:

1. используя функцию;
2. без использования функции;
3. получение пользовательского ввода.

Метод 1: с использованием цикла for

Цикл for используется в алгоритме пузырьковой сортировки для многократного прохода по списку, сравнения соседних элементов и замены их при необходимости.

Давайте рассмотрим пример и поймем, как цикл for можно использовать в программе Python для пузырьковой сортировки:

Пример.

Код:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
# Example usage:
unsorted_list = [5, 2, 9, 1, 5]
sorted_list = bubble_sort(unsorted_list)
print("Sorted list:", sorted_list)

Вывод: во внутреннем цикле for в Python условный оператор if сравнивает текущий элемент со следующим элементом. Если текущий элемент больше следующего элемента, элементы меняются местами с помощью оператора присваивания(=) в Python.

Комбинация внешнего и внутреннего циклов for в пузырьковой сортировке позволяет алгоритму постепенно сортировать список, сравнивая и меняя местами соседние элементы, пока весь список в Python не будет отсортирован в порядке возрастания.

Sorted list: [1, 2, 5, 5, 9]

Таким образом, мы можем просто использовать цикл for или, скажем, вложенный цикл for, чтобы написать программу на Python для пузырьковой сортировки.

Метод 2: с использованием цикла while

Использование цикла while для пузырьковой сортировки в Python предполагает перебор списка до тех пор, пока не перестанут требоваться замены, что указывает на то, что список отсортирован.

Вот объяснение того, как пузырьковая сортировка может быть реализована в Python с помощью цикла while, на примере:

my_list = [64, 34, 25, 12, 22, 11, 90]

n = len(my_list)
swapped = True  # Initialize swapped as True to enter the loop

while swapped:
    swapped = False  # Reset swapped for this pass
    for i in range(1, n):
        if my_list[i - 1] > my_list[i]:
            # Swap the elements
            my_list[i - 1], my_list[i] = my_list[i], my_list[i - 1]
            swapped = True  # Set swapped to True if a swap occurs

# Print the sorted list
print("Sorted list is:", my_list)

Вывод: Цикл while продолжается до тех пор, пока при проходе по списку больше не потребуется никаких замен, что указывает на то, что список Python отсортирован. Внутри цикла while внутренний цикл for перебирает список, сравнивая соседние элементы и меняя их местами при необходимости.

Если во время прохода выполняется замена, флаг swapped устанавливается в значение True, что указывает на то, что может потребоваться еще один проход. После завершения цикла while список в Python будет отсортирован по возрастанию.

Sorted list is: [11, 12, 22, 25, 34, 64, 90]

Таким образом, мы можем просто использовать цикл while с циклом for и замененным флагом и написать программу на Python для пузырьковой сортировки.

Метод 3: с использованием понимания списка

Понимание списков — это краткий и удобочитаемый способ создания списков в Python. Это позволяет нам генерировать новый список в Python, применяя выражение к каждому элементу в существующей итерации и дополнительно применяя условие для фильтрации элементов.

Понимание списков обычно не используется для алгоритмов сортировки, таких как пузырьковая сортировка, поскольку пузырьковая сортировка предполагает замену элементов на месте, что не очень подходит для декларативного характера понимания списков. Однако мы можем использовать списки для других операций, связанных с сортировкой, таких как создание отсортированной копии списка в Python или фильтрация элементов на основе определенных условий.

Пример: давайте воспользуемся генераторами списков, чтобы создать новый отсортированный список в Python из существующего списка, не изменяя исходный список. По сути, мы реализуем упрощенную версию программы Python для пузырьковой сортировки с использованием списков:

original_list = [64, 34, 25, 12, 22, 11, 90]
# List comprehension to create a sorted copy
sorted_list = [x for x in sorted(original_list)]
# Print the sorted list
print("Original list:", original_list)
print("Sorted list:", sorted_list)

Вывод: В этом коде мы начинаем со списка Python original_list, содержащего неотсортированные элементы. Мы используем функцию sorted(), которая возвращает новый отсортированный список без изменения исходного списка. Затем мы используем понимание списка для создания списка Python sorted_list, который содержит отсортированные элементы. Наконец, мы печатаем исходные и отсортированные списки.

Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]

Этот код не реализует программу Bubble Sort Python, использующую генераторы списков, но использует генераторы списков в сочетании с функцией sorted() для создания отсортированной копии исходного списка в Python.

Способ 1: с использованием функции

Вот реализация алгоритма пузырьковой сортировки с использованием функции Python.

Код:

def bubble_sort(input_list):
    n = len(input_list)
    for _ in range(n):
        swapped = False
        for i in range(1, n):
            if input_list[i - 1] > input_list[i]:
                # Swap the elements
                input_list[i - 1], input_list[i] = input_list[i], input_list[i - 1]
                swapped = True
        # If no swaps were made in this pass, the list is sorted
        if not swapped:
            break
    return input_list

input_list = [64, 16, 5, 41, 29, 20]
sorted_list = bubble_sort(input_list)
# Print the sorted array
print("Sorted list is:", sorted_list)

Вывод: мы только что применили метод цикла for внутри функции Python, чтобы написать программу Python для пузырьковой сортировки.

Вот как мы создаем программу пузырьковой сортировки Python с функцией.

Sorted list is: [5, 16, 20, 29, 41, 64]

Способ 2: без использования функции

Мы можем реализовать алгоритм пузырьковой сортировки на Python без использования отдельной функции.

Код:

My_list = [64, 34, 25, 12, 22, 11, 90]
n = len(My_list)
for i in range(n):
    # Flag to optimize the algorithm
    swapped = False
    for j in range(0, n-i-1):
        if My_list[j] > My_list[j+1]:
            # Swap the elements
            My_list[j], My_list[j+1] = My_list[j+1], My_list[j]
            swapped = True
    # If no two elements were swapped in the inner loop, the list is already sorted
    if not swapped:
        break

print("Sorted list is:", My_list)

Вывод: это то же самое, что и цикл for, но он также содержит замененный флаг для написания программы Python для пузырьковой сортировки без функции.

Sorted list is: [11, 12, 22, 25, 34, 64, 90]

Способ 3: с пользовательским вводом

Мы можем изменить программу Python, чтобы она принимала пользовательский ввод для списка, который необходимо отсортировать пузырьком.

Код:

# Taking user input for the list of numbers
input_str = input("Enter a list of numbers separated by spaces: ")
input_list = [int(x) for x in input_str.split()]

n = len(input_list)
for i in range(n):
    swapped = False
    for j in range(0, n-i-1):
        if input_list[j] > input_list[j+1]:
            # Swap the elements
            input_list[j], input_list[j+1] = input_list[j+1], input_list[j]
            swapped = True
    if not swapped:
        break

print("Sorted list is:", input_list)

Вывод: в этом случае мы также использовали метод цикла for для пузырьковой сортировки в Python. Но. вместо предоставления списка, который будет отсортирован, мы предоставляем код, который будет принимать вводимые пользователем данные и создавать список с помощью метода понимания списка в Python.

Enter a list of numbers separated by spaces: 16 64 5 29 20 41 111 102
Sorted list is: [5, 16, 20, 29, 41, 64, 102, 111]