Bubble Sort

Проблема

Дан массив чисел в произвольном порядке, например [5, 2, 8, 1]. Нужно упорядочить его по возрастанию. Простейшая идея: брать пары соседних элементов и менять их местами, если левый больше правого. Вопрос в том, как повторять это действие так, чтобы за конечное число проходов массив гарантированно стал отсортированным.

Решение

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

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

Представь, что у тебя в руке набор игральных карт в случайном порядке, и ты хочешь разложить их по возрастанию. Самый интуитивный способ - брать пару соседних карт и, если левая больше правой, менять их местами. Именно это и делает пузырьковая сортировка: она идёт по массиву слева направо, сравнивая каждую пару соседних элементов и переставляя их, если они стоят не в том порядке.

После первого полного прохода происходит кое-что гарантированное: самый большой элемент оказывается в конце массива. Почему? При каждом сравнении большее значение «толкается» вправо. Как только самый большой элемент встречает левого соседа, он всегда оказывается больше - и продолжает двигаться вправо до самого конца. Этот эффект дал алгоритму название: большие элементы «всплывают» вверх, как пузырьки в воде.

Второй проход начинается с тем же правилом, но правая граница сдвигается: последний элемент уже на месте. После k-го прохода k наибольших элементов стоят на своих окончательных позициях. Это и есть инвариант цикла: слева от границы ещё нужно работать, справа - уже всё правильно. Поэтому в худшем случае нужно n-1 проходов: после каждого граница сдвигается влево на одну позицию.

Но что если массив уже почти отсортирован? Здесь вступает в игру флаг swapped. Перед каждым проходом он сбрасывается в false. Если произошла хотя бы одна перестановка, флаг становится true. Если после прохода он остался false - все соседние пары уже стоят правильно, массив отсортирован, и алгоритм завершается досрочно. Именно поэтому лучший случай достигает O(n): нужен ровно один проход без единой перестановки.

Теперь о худшем случае O(n²). Он возникает, когда массив отсортирован в обратном порядке. Рассмотрим [4, 3, 2, 1]. Элемент 1 стоит в конце, а должен быть в начале. За один проход он сдвигается максимум на одну позицию влево - пузырьковая сортировка перемещает элементы влево только на один шаг за проход. Такой медленный элемент в правой части называют «черепахой» (turtle). Черепаха вынуждает алгоритм делать n-1 проходов даже тогда, когда 99% массива уже отсортировано.

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

Пузырьковая сортировка является устойчивой (stable): если два элемента одинаковы по значению, они сохраняют исходный относительный порядок. Устойчивость обеспечивается строгим условием обмена: a[j] > a[j+1]. При равенстве (a[j] === a[j+1]) обмен не происходит, левый из равных всегда остаётся левее. Это важно, например, при сортировке списка людей сначала по фамилии, а затем по имени - устойчивая сортировка сохранит порядок внутри одинаковых фамилий.

Нюансы выбора

Учебный инструмент - пузырьковая идеальна для объяснения самой идеи сортировки сравнением: механика прозрачна, анимация «всплытия» интуитивно понятна, и её можно нарисовать на доске за минуту. Практически все курсы по алгоритмам начинают именно с неё - и это оправданно.

Production-код - применима только для очень маленьких массивов (n < 10-15) или данных, которые заведомо почти отсортированы. При n < 10 разница между O(n²) и O(n log n) практически не ощутима: константы и оверхед вызова съедают асимптотическое преимущество.

Когда писать что-то другое - для массивов от 50 элементов и выше всегда quicksort или merge sort. Для встроенных систем с дорогими операциями записи (EEPROM, флеш-память) - сортировка выбором, потому что она гарантирует не более n перестановок против O(n²) у пузырьковой. Если нужна устойчивость и скорость одновременно - merge sort или Timsort.

Три оси сравнения - скорость, память, простота. По скорости: пузырьковая хуже insertion sort на практике, хуже selection sort при большом числе записей, хуже merge/quicksort асимптотически. По памяти: O(1) - наравне с insertion и selection sort, лучше merge sort с его O(n). По простоте кода: примерно равна insertion sort, проще merge sort.

Насколько именно ощутим этот разрыв на практике (причина разобрана в разделе «Как это работает»)? На почти отсортированных массивах insertion sort обычно в 1.5-2x быстрее пузырьковой - каждый обмен там это 3 операции записи вместо прямого сдвига на одну позицию.

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

Краткая таблица - когда выбрать пузырьковую вместо соседей. Bubble vs Insertion: при n < 10 или для обучения; insertion лучше на почти отсортированных при n > 20. Bubble vs Selection: если нужна устойчивость и записи не дорогие; selection лучше когда записи дорогие. Bubble vs Merge: merge всегда быстрее при n > 15-20, но требует O(n) памяти. Bubble vs Quick: quick быстрее в среднем, но нестабилен и O(n²) в худшем.

Примеры в коде

На практике пузырьковая сортировка встречается редко, но её идея повлияла на более практичные варианты. Самый известный - Cocktail Shaker Sort (шейкерная, или двунаправленная пузырьковая). Она чередует направление прохода: сначала слева направо (выталкивая большие элементы вправо), потом справа налево (выталкивая маленькие элементы влево). Это напрямую решает проблему «черепах».

Как именно шейкерная ускоряет работу с черепахами? Возьмём [2, 3, 4, 5, 1], где 1 - черепаха в конце. Обычная пузырьковая потратит 4 прохода, чтобы сдвинуть 1 в начало, по одной позиции за проход. Шейкерная на обратном проходе (справа налево) сразу переместит 1 на несколько позиций. Асимптотика остаётся O(n²), но на практике шейкерная заметно быстрее на случайных данных с малыми элементами у правого края.

Исторически пузырьковая входила в стандартные реализации языков до появления Timsort и introsort. Java до версии 7 использовала модифицированную merge sort в Arrays.sort(). В Python до 2.3 list.sort() использовала sample sort. После 2002 года Timsort (разработанный Тимом Петерсом) стал де-факто стандартом в Python и Java 7+, затем V8 перешёл на него в 2019 году. Пузырьковая давно уступила место гибридам.

Где живёт пузырьковая идея сегодня? Timsort использует insertion sort для маленьких подмассивов (run-ов), а insertion sort на почти отсортированных данных работает аналогично пузырьковой. Comb Sort - ещё один вариант: вместо сравнения соседей (gap=1) он начинает с большого шага, постепенно уменьшая его до 1. Это устраняет черепах гораздо эффективнее - так же, как Shell Sort применил ту же идею к insertion sort.

Встроенные системы - одна из ниш, где пузырьковая изредка встречается: на микроконтроллерах для малых буферов сенсорных данных (5-15 значений). Например, медианный фильтр (STM32, Arduino): собери N последних измерений, отсортируй, возьми средний элемент. При N=7 пузырьковая с флагом занимает ~42 байта кода против ~120 байт у quicksort на ARM Cortex-M0 - и этот размер иногда решает, влезет ли прошивка во флеш.

Крупные open-source проекты сохраняют пузырьковую идею в виде наследников: CPython (Objects/listobject.c) использует Timsort, чья логика работы с run-ами наследует insertion sort; ядро Linux (lib/sort.c) - heapsort с оптимизациями; SQLite (src/vdbesort.c) - внешнюю сортировку на основе merge sort. Сама пузырьковая в продакшн-коде крупных проектов не встречается, но понимание её механики необходимо для понимания гибридов.

Культурный след: пузырьковая остаётся стандартным примером в академических работах по сложности алгоритмов. В 1988 году Кнут в TAOCP назвал её «худшим из практических алгоритмов». В 2000-х Барак Обама, отвечая на вопрос о лучшем алгоритме сортировки, заявил: «bubble sort is the wrong answer». Этот момент точно формулирует суть: пузырьковая - педагогический артефакт, а не рабочий инструмент.

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

• Учебный пример - для объяснения самой идеи сортировки сравнением до перехода к более сложным алгоритмам.
• Маленькие и почти отсортированные массивы - при n < 10-15, где простота кода важнее асимптотики.

Примеры из практики

• Учебные курсы по алгоритмам - почти всегда первый алгоритм сортировки, который объясняют, благодаря наглядности идеи «всплытия».
• Встроенные системы - где O(1) дополнительной памяти важнее скорости на небольшом наборе данных.