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

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

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

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

Название “пузырьковая сортировка” происходит от того, что мелкие элементы “всплывают” в верхнюю часть списка (начало массива), а крупные “опускаются” в нижнюю часть (конец массива).

Вот пошаговое объяснение того, как это работает:

1. Начните с первых двух элементов и сравните их.
2. Если первый элемент больше второго, то они меняются местами.
3. Перейдите к следующей паре элементов и повторите процесс.
4. Продолжайте менять местами элементы до тех пор, пока самый большой элемент не окажется в нужном месте в конце списка.
5. Уменьшите диапазон элементов на единицу (так как самый большой теперь отсортирован) и повторите процесс для оставшихся элементов.

Реализация пузырьковой сортировки на Python

Рассмотрим код на языке Python, выполняющий пузырьковую сортировку:

def bubblesort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):
        # Last i elements are already in place, so the inner loop can skip them
        for j in range(n - i - 1):
            # Traverse the array from 0 to n-i-1 and swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    
    return arr

Как работает этот код?

1. Определим функцию bubblesort, которая принимает массив arr в качестве аргумента.
2. Сохраняем длину массива в переменной n, потому что нам нужно знать, когда остановить процесс сортировки.
3. Мы используем вложенный цикл, где внешний цикл представляет собой количество проходов, необходимых для сортировки массива, а внутренний проходит по сравниваемым элементам.
4. Во внутреннем цикле мы выполняем сравнение: if arr[j] > arr[j+1]:. Таким образом мы проверяем, больше ли текущий элемент, чем следующий элемент.
5. Если текущий элемент больше, то мы меняем местами два элемента, используя распаковку кортежа: arr[j], arr[j+1] = arr[j+1], arr[j].
6. После каждого прохода наибольший элемент текущего подсписка “всплывает” на свое место, и на следующей итерации его можно не учитывать, чего мы и добиваемся, уменьшая диапазон внутреннего цикла.
7. Процесс продолжается до тех пор, пока массив не будет отсортирован.
8. Возвращаем отсортированный массив.

Заключение

Пузырьковая сортировка, хотя и не является самым эффективным алгоритмом для больших наборов данных из-за своей сложности O(n²), является отличным образовательным инструментом для понимания фундаментальных концепций сортировки. Благодаря своей простоте он идеально подходит для небольших списков и для учебных целей.

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

Перевод статьи «Bubblesort algorithm with Python».