Сортировка пузырьком в Python

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

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

Сортировка пузырьком — это алгоритм, который упорядочивает элементы списка путём последовательного сравнения и обмена соседних элементов. Смысл названия заключается в том, что как самые большие элементы «всплывают» вверх списка (подобно пузырькам в воде), так и самые маленькие элементы постепенно перемещаются к началу списка.

Принцип работы заключается в том, что за каждый проход по списку сравниваются соседние элементы. Если они расположены в неправильном порядке (например, в случае сортировки по возрастанию первый элемент больше второго), они меняются местами. Таким образом, за одну итерацию прохода по всему списку на своё место становится один из элементов (самый большой в случае сортировки по возрастанию). Процесс повторяется, пока весь список не будет отсортирован.

Пошаговое описание алгоритма

Сортировка пузырьком можно представить как серию итераций, где на каждой итерации выполняются следующие шаги:

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

Пример работы алгоритма на списке [5, 3, 8, 4, 2]:

• 1-я итерация:
  • Сравниваем 5 и 3: меняем их местами, получаем [3, 5, 8, 4, 2].
  • Сравниваем 5 и 8: ничего не меняем, [3, 5, 8, 4, 2].
  • Сравниваем 8 и 4: меняем их местами, [3, 5, 4, 8, 2].
  • Сравниваем 8 и 2: меняем их местами, [3, 5, 4, 2, 8].
• 2-я итерация:
  • Сравниваем 3 и 5: ничего не меняем, [3, 5, 4, 2, 8].
  • Сравниваем 5 и 4: меняем их местами, [3, 4, 5, 2, 8].
  • Сравниваем 5 и 2: меняем их местами, [3, 4, 2, 5, 8].
• 3-я итерация:
  • Сравниваем 3 и 4: ничего не меняем, [3, 4, 2, 5, 8].
  • Сравниваем 4 и 2: меняем их местами, [3, 2, 4, 5, 8].
• 4-я итерация:
  • Сравниваем 3 и 2: меняем их местами, [2, 3, 4, 5, 8].

В результате список отсортирован, и алгоритм завершает свою работу.

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

Теперь, когда мы разобрались с теорией и принципами работы сортировки пузырьком, давайте рассмотрим, как этот алгоритм можно реализовать на языке 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

# Пример использования функции
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = bubble_sort(unsorted_list)
print("Отсортированный список:", sorted_list)

Пояснение работы кода

1. Функция bubble_sort принимает список arr в качестве аргумента.
2. Переменная n хранит длину списка, что необходимо для определения количества итераций.
3. Первый цикл for i in range(n) управляет количеством проходов по списку. На каждом шаге на своём месте оказывается один элемент, поэтому мы уменьшаем количество элементов, которые нужно проверить, на каждом следующем проходе.
4. Внутренний цикл for j in range(0, n-i-1) проходит по списку и сравнивает соседние элементы. Если текущий элемент больше следующего, они меняются местами.
5. Обмен элементов arr[j], arr[j+1] = arr[j+1], arr[j] происходит, если текущий элемент больше следующего. Это и есть тот самый «пузырёк», который поднимается вверх.
6. После завершения всех итераций функция возвращает отсортированный список.

Оптимизация алгоритма

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

Пример кода

def optimized_bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        # Внутренний цикл для сравнения элементов
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # Если обменов не было, выходим из цикла
        if not swapped:
            break
    return arr

# Пример использования функции
unsorted_list = [64, 34, 25, 12, 22, 11, 90]
sorted_list = optimized_bubble_sort(unsorted_list)
print("Отсортированный список:", sorted_list)

Пояснение работы оптимизированного кода

1. Переменная swapped введена для отслеживания, происходил ли обмен на текущей итерации. Изначально она установлена в False перед началом внутреннего цикла.
2. Внутренний цикл проверяет и меняет местами элементы, если это необходимо. При каждом обмене swappedустанавливается в True.
3. Проверка if not swapped:. После завершения внутреннего цикла происходит проверка: если обменов не было (т.е. swapped остался равен False), внешний цикл прерывается с помощью break. Это означает, что массив уже отсортирован, и дальнейшая работа алгоритма не требуется.

Преимущества оптимизации

• Сокращение времени выполнения: Оптимизация особенно эффективна для почти отсортированных массивов. В лучшем случае, если массив уже отсортирован, сложность алгоритма снижается до O(n).
• Простота реализации: Добавление флага swapped и условия выхода минимально усложняет код, сохраняя при этом его читаемость и эффективность.