Сортировка пузырьком (bubble sort) — это простой алгоритм сортировки, который упорядочивает массив попарным сравнением соседних элементов и меняет их местами, если они стоят в неправильном порядке. Название пузырьковая сортировка появилось потому, что большие значения при каждом проходе постепенно «всплывают» к концу массива, как пузырьки воздуха в воде. Ниже разберем, как алгоритм работает по шагам, посчитаем его сложность, покажем оптимизацию с флагом и рабочую реализацию на Python, а в конце сравним пузырьковую сортировку с другими методами.
Содержание
Как работает сортировка пузырьком
Идея алгоритма сводится к повторяющимся проходам по массиву. За один проход мы идем слева направо и сравниваем каждую пару соседних элементов.
- Если левый элемент больше правого — меняем их местами.
- Если левый меньше или равен правому — оставляем как есть и переходим к следующей паре.
За первый полный проход самый большой элемент гарантированно оказывается в конце массива. За второй проход на предпоследнее место встает второй по величине элемент, и так далее. Поэтому с каждым проходом «хвост» массива уже отсортирован, и зону сравнения можно сокращать.
Проходы повторяются до тех пор, пока за очередной проход не случится ни одного обмена. Отсутствие обменов означает, что все соседние пары уже стоят в правильном порядке, а значит, весь массив отсортирован.
Пошаговый разбор одного примера
Возьмем массив [5, 1, 4, 2, 8] и отсортируем его по возрастанию. Жирным отметим пару, которую сравниваем.
Проход 1:
- 5, 1 -> 5 больше 1, меняем:
[1, 5, 4, 2, 8] - 5, 4 -> меняем:
[1, 4, 5, 2, 8] - 5, 2 -> меняем:
[1, 4, 2, 5, 8] - 5, 8 -> порядок верный, оставляем:
[1, 4, 2, 5, 8]
В конец «всплыло» число 8 — самое большое. Дальше его можно не трогать.
Проход 2 (последний элемент уже на месте):
- 1, 4 -> оставляем
- 4, 2 -> меняем:
[1, 2, 4, 5, 8] - 4, 5 -> оставляем
Проход 3:
- 1, 2 -> оставляем
- 2, 4 -> оставляем
За третий проход не было ни одного обмена — массив отсортирован: [1, 2, 4, 5, 8].
Сложность O(n^2)
Разберем, почему у пузырьковой сортировки такая оценка. Здесь n — число элементов в массиве.
В худшем и среднем случае алгоритм делает около n проходов, и внутри каждого — до n сравнений. Итого порядка n * n операций, то есть сложность по времени равна O(n^2). Для массива из 10 элементов это десятки операций, а для 10 000 элементов — уже около ста миллионов, поэтому на больших данных пузырьковая сортировка работает медленно.
В лучшем случае, когда массив уже отсортирован, оптимизированная версия (с флагом обменов, см. ниже) сделает всего один проход без единого обмена и завершится. Это дает лучшую оценку O(n).
По памяти алгоритм очень экономный: он сортирует массив «на месте» и не заводит вспомогательных структур, зависящих от размера данных. Дополнительная память — O(1).
| Случай | Число сравнений | Сложность по времени |
|---|---|---|
| Лучший (массив уже отсортирован) | ~n | O(n) |
| Средний | ~n^2 / 2 | O(n^2) |
| Худший (массив отсортирован наоборот) | ~n^2 / 2 | O(n^2) |
Реализация на Python с оптимизацией флагом
Наивная версия всегда делает фиксированное число проходов, даже если массив давно готов. Оптимизация добавляет булеву переменную swapped: если за проход не было ни одного обмена, выходим досрочно. Плюс сокращаем внутренний цикл — хвост длиной i уже отсортирован.
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
# хвост длиной i уже отсортирован, поэтому -i
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
print(bubble_sort([5, 1, 4, 2, 8]))Фактический вывод программы:
[1, 2, 4, 5, 8]
Обмен элементов сделан через множественное присваивание arr[j], arr[j + 1] = arr[j + 1], arr[j] — это идиома Python, временная переменная не нужна. В других языках (C, Java) для обмена обычно заводят вспомогательную переменную.
Частая ошибка: выход за границу массива
Типичная ошибка новичка — написать внутренний цикл до range(n). Тогда на последней итерации обращение к arr[j + 1] выходит за пределы массива.
Неверный код:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n): # ошибка: j дойдет до n-1
if arr[j] > arr[j + 1]: # arr[j+1] выходит за границу
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([5, 1, 4, 2, 8]))Фактический результат:
IndexError: list index out of range
Исправление — ограничить внутренний цикл до range(n - 1) (или range(n - 1 - i) в оптимизированной версии), чтобы пара arr[j] и arr[j + 1] всегда оставалась внутри массива.
Плюсы и минусы
Сильные стороны:
- Очень простая логика — алгоритм легко понять и написать без ошибок.
- Сортирует «на месте», расход дополнительной памяти O(1).
- Устойчивость: равные элементы не меняются местами, их взаимный порядок сохраняется.
- На почти отсортированных данных оптимизированная версия быстро завершается за счет флага.
Слабые стороны:
- Медленная на больших массивах из-за сложности O(n^2).
- В реальных проектах почти всегда проигрывает сортировкам с оценкой O(n log n).
- Много обменов по сравнению, например, с сортировкой выбором, которая на том же массиве переставляет элементы реже.
Сравнение с другими сортировками
Пузырьковая сортировка — учебный алгоритм. Для сравнения приведем оценки соседних методов; n — число элементов.
| Алгоритм | Лучший | Средний | Худший | Память | Устойчивость |
|---|---|---|---|---|---|
| Пузырьком | O(n) | O(n^2) | O(n^2) | O(1) | да |
| Вставками | O(n) | O(n^2) | O(n^2) | O(1) | да |
| Выбором | O(n^2) | O(n^2) | O(n^2) | O(1) | нет |
| Слиянием | O(n log n) | O(n log n) | O(n log n) | O(n) | да |
| Быстрая (Хоара) | O(n log n) | O(n log n) | O(n^2) | O(log n) | нет |
Практический вывод из таблицы: если данных много, берут сортировку слиянием или быструю. Встроенные функции (в Python это sorted() и метод list.sort()) используют алгоритм Timsort со сложностью O(n log n) и в реальном коде почти всегда предпочтительнее ручного пузырька.
Выводы
- Сортировка пузырьком сравнивает соседние элементы попарно и меняет их местами, пока за проход не останется ни одного обмена.
- Сложность в среднем и худшем случае — O(n^2), поэтому на больших массивах алгоритм медленный.
- Оптимизация флагом обменов дает лучший случай O(n) на уже отсортированных данных и позволяет выйти досрочно.
- Расход дополнительной памяти — O(1): сортировка идет «на месте».
- Алгоритм устойчив: равные элементы сохраняют исходный взаимный порядок.
- В рабочих проектах вместо пузырька используют встроенные сортировки или методы с оценкой O(n log n); пузырьковая сортировка ценна прежде всего как учебный пример.
Где применяется / связь с практикой
На практике пузырьковую сортировку почти не применяют для боевых задач — ее вытесняют более быстрые алгоритмы. Зато она незаменима в обучении: на ней удобно объяснять базовые идеи сортировок, инвариант «за проход самый большой всплывает в конец» и оценку сложности. Понимание того, как устроен простой алгоритм и почему он медленный, помогает осознанно выбирать структуры данных и методы в реальном коде.
Освойте тему на практике
Разобраться в алгоритмах и их сложности системно помогает курс algorithm: там сортировки, поиск и оценки O-нотации разбирают на практике. Познакомиться с форматом и темами заранее можно на бесплатных вебинарах.
Смежные темы: Сортировка слиянием: описание и реализация, Сортировка Хоара и другие способы сортировки массивов, Сортировка: основные принципы.
FAQ
Устойчива ли сортировка пузырьком?
Да. Обмен происходит только при строгом условии «левый больше правого», а равные элементы местами не меняются — их исходный взаимный порядок сохраняется.
Когда пузырьковую сортировку имеет смысл применять?
На небольших или почти отсортированных массивах и в учебных целях. Для больших объемов данных берут более быстрые алгоритмы (слияние, быструю) или встроенные функции языка.
Чем сортировка пузырьком отличается от сортировки выбором?
Пузырьком сравнивает и меняет местами соседние пары за каждый проход, поэтому обменов много. Сортировка выбором за проход находит минимум и делает всего один обмен, но при этом она неустойчива.
