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

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

¶Принцип работы

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

Ключевое свойство: после k-го прохода последние k элементов уже стоят на своих местах, поэтому каждый следующий проход можно сокращать на один элемент.

¶Пример

Исходный массив: [5, 1, 4, 2, 8]

Первый проход:

• 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]

Восьмёрка заняла последнюю позицию. Далее проходы повторяются для первых четырёх элементов, затем трёх и так далее.

¶Псевдокод

`` процедура пузырёк(A): n = длина(A) для i от 0 до n-2: для j от 0 до n-2-i: если A[j] > A[j+1]: обменять A[j] и A[j+1] ``

¶Сложность

Квадратичная сложность делает алгоритм неэффективным на больших массивах. При n = 1000 число сравнений в среднем достигает порядка 500 тысяч, тогда как быстрая сортировка справляется за десятки тысяч операций.

¶Оптимизации

• Флаг обмена. Если за очередной проход не произошло ни одного обмена, массив уже отсортирован, и работу можно завершить досрочно. Это даёт сложность O(n) на упорядоченных данных.
• Сокращение диапазона. Каждый проход уменьшает область просмотра, поскольку хвост массива уже отсортирован.
• Шейкерная сортировка. Двунаправленный вариант: проходы выполняются поочерёдно слева направо и справа налево, что ускоряет обработку массивов с «тяжёлыми» элементами на одном из концов.

¶Свойства

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

¶Применение

В практической разработке алгоритм почти не используется из-за низкой производительности. Его применяют:

• в учебных курсах как первый пример алгоритма сортировки и иллюстрацию анализа сложности;
• для сортировки очень малых массивов (до 10–20 элементов), где накладные расходы сложных алгоритмов сопоставимы;
• в задачах, где важна простота и наглядность кода, а объём данных невелик;
• как составная часть гибридных схем в некоторых встраиваемых системах.

В стандартных библиотеках языков программирования пузырьковая сортировка не входит в базовые наборы функций: вместо неё применяются быстрая сортировка, сортировка слиянием, Timsort и другие.

¶Место среди алгоритмов

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

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

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