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

Сортировка пузырьком (Bubble Sort): идея, пошаговый разбор прохода, код на Python, сложность O(n²) и оптимизация с досрочным выходом.

Сортировка пузырьком — один из самых простых алгоритмов сортировки. Она многократно проходит по массиву и меняет местами соседей, стоящих в неправильном порядке. Крупные элементы «всплывают» вправо — как пузырьки воздуха.

Сложность: O(n²) в среднем и худшем случае; O(n) в лучшем (уже отсортированный массив с оптимизацией).

Идея алгоритма

На каждом «проходе» мы сравниваем каждую пару соседних элементов. Если левый больше правого — меняем их местами. После первого прохода самый большой элемент окажется на последней позиции. После второго — второй по величине займёт предпоследнюю позицию. И так далее.

Пошаговый разбор

Возьмём массив [5, 3, 8, 1, 2]. Отследим первый проход:

Шаг	Сравниваем	Обмен?	Массив после шага
1	5 и 3	да	[3, 5, 8, 1, 2]
2	5 и 8	нет	[3, 5, 8, 1, 2]
3	8 и 1	да	[3, 5, 1, 8, 2]
4	8 и 2	да	[3, 5, 1, 2, 8]

После первого прохода 8 («самый тяжёлый пузырь») встало на своё место. Продолжаем, пока массив не будет упорядочен.

Код

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):   # каждый раз зона сравнений короче
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:               # проход без обменов — массив готов
            break
    return arr

data = [5, 3, 8, 1, 2]
print(bubble_sort(data))

Вывод:

[1, 2, 3, 5, 8]

Флаг swapped — это оптимизация досрочного выхода: если за целый проход не было ни одного обмена, массив уже отсортирован и смысла продолжать нет.

Сложность и свойства

Случай	Сравнений	Перестановок
Лучший (отсортирован)	O(n)	0
Средний	O(n²)	O(n²)
Худший (обратный порядок)	O(n²)	O(n²)

Память: O(1) — сортировка на месте (in-place), дополнительных массивов нет. Алгоритм устойчивый: равные элементы не меняют взаимного порядка.

Когда применять

На практике сортировку пузырьком почти не используют: она медленна на больших данных. Её ценность — учебная: алгоритм отлично иллюстрирует саму идею сортировки обменами. Применима разве что к очень коротким или почти отсортированным массивам.

Коротко

Пузырьковая сортировка сравнивает и меняет местами соседей, «всплывая» крупными элементами вправо.
Сложность O(n²) в среднем и худшем случае, O(n) в лучшем с оптимизацией swapped.
Алгоритм устойчивый и работает in-place (O(1) памяти).
Используется главным образом в учебных целях.