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

Сортировка пузырьком (англ. bubble sort) - один из простейших алгоритмов сортировки. Из-за простоты реализации, её часто просят написать на собеседовании на должность джуниор разработчика. Этот алгоритм имеет ряд более эффективных модификаций, включая широко распространенный метод быстрой сортировки (англ. quicksort).

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

Давайте разберем работу этого алгоритма на следующем списке:

[6, 1, 3, 4, 2, 5]

Для начала сравним первые два значения. Если второе значение больше первого - меняем их местами.

[1, 6, 3, 4, 2, 5]

Дальше смещаемся на один элемент правее, и повторяем, пока не дойдем до конца списка.

[1, 3, 6, 4, 2, 5]
[1, 3, 4, 6, 2, 5]
[1, 3, 4, 2, 6, 5]
[1, 3, 4, 2, 5, 6]

Малые числа сместились на одну позицию, а наибольшее "всплыло" как пузырек, и оказалось на своем месте. Теперь можно повторять те же действия, уменьшая количество сравнений на каждом этапе на единицу. Посмотрим, как заканчиваются последующие этапы:

• Шаг 2.4: [1, 3, 2, 4, 5, 6]
• Шаг 3.3: [1, 2, 3, 4, 5, 6]
• Шаг 4.2: [1, 2, 3, 4, 5, 6]

Если на каком-то этапе не было перестановок (в примере - на четвертом), нужно остановить алгоритм. Тогда в лучшем случае (если список уже отсортирован) алгоритм отработает за один этап.

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

• Список: [5, 4, 3, 2, 1]
• Шаг 1.4: [4, 3, 2, 1, 5]
• Шаг 2.3: [3, 2, 1, 4, 5]
• Шаг 3.2: [2, 1, 3, 4, 5]
• Шаг 4.1: [1, 2, 3, 4, 5]

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

Реализация на Python

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

def bubble_sort(orig):
    # копируем список, чтобы не менять оригинал
    lst = orig.copy()
    # n - длина списка
    n = len(lst)
    # Проходимся по списку n раз
    for i in range(n):
        swap = False
        # Последние i элементов уже на своих местах - исключаем из цикла
        for j in range(n - i - 1):
            # Меняем местами элементы пары, если порядок неверный
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]
                # Меняем значение swap, если элементы менялись местами
                swap = True
        # Останавливаем цикл, если элементы не менялись местами
        if swap is False:
            break
    return lst

Переменная swap будет менять значение на True если элементы менялись местами. Если этого не произошло, значит список отсортирован. В этом случае цикл прерывается.

Попробуем запустить нашу функцию:

a = [9, 2, 1, 6, 3, 4, 1, 3, 9, 5, 8, 7, 5]
print(bubble_sort(a))

Если вы все сделали правильно, список a будет отсортирован:

[1, 1, 2, 3, 3, 4, 5, 5, 6, 7, 8, 9, 9]

Заключение

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

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