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

TL;DR

Сортировка пузырьком (bubble sort) многократно проходит по массиву, сравнивая соседние элементы и меняя их, если они стоят не по порядку; за каждый проход наибольший элемент «всплывает» в конец рассматриваемой части. Алгоритм работает на месте ([math]\displaystyle{ O(1) }[/math] памяти) и устойчив, а с флагом раннего выхода становится адаптивным: на уже отсортированном массиве делает [math]\displaystyle{ n-1 }[/math] сравнение и завершается. Но в среднем и худшем случаях — [math]\displaystyle{ \Theta(n^2) }[/math] сравнений и до [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] обменов, что делает его самым «затратным» из элементарных сортировок. Поэтому на практике пузырёк почти не используется: он ценен как учебный пример инвариантов и адаптивности, а также как основа для comb sort и шейкерной сортировки.

Свойство	Значение
Класс	Сортировка сравнением; обменная (exchange sort); на месте
Идея	Сравнение соседних пар и обмен «неправильных»
Лучший случай	[math]\displaystyle{ \Theta(n) }[/math] с флагом ([math]\displaystyle{ n-1 }[/math] сравнений), [math]\displaystyle{ \Theta(n^2) }[/math] без
Средний / худший	[math]\displaystyle{ \Theta(n^2) }[/math]
Обменов	до [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] (много!)
Память	[math]\displaystyle{ O(1) }[/math]
Устойчивость	да
Адаптивность	да, с флагом раннего выхода
Варианты	шейкерная, comb sort, сужение по последнему обмену
Родственники	вставки, выбор, Шелл
Где встречается	обучение, детект «отсортировано», comb sort

Определения

Сортировка пузырьком — алгоритм, который выполняет несколько проходов по массиву; на проходе сравниваются пары соседних элементов [math]\displaystyle{ (a[j], a[j+1]) }[/math], и при [math]\displaystyle{ a[j] \gt a[j+1] }[/math] они меняются местами.

Проход (pass). Один линейный проход по текущей части массива. После [math]\displaystyle{ k }[/math]-го прохода последние [math]\displaystyle{ k }[/math] элементов стоят на своих местах, поэтому граница прохода сужается на единицу.

Обменный алгоритм (exchange sort). Класс сортировок, переставляющих элементы обменом соседних; пузырёк — наиболее известный представитель (иногда его зовут sinking sort — «сортировка погружением», если смотреть на всплывающий вниз максимум).

На месте (in-place) — [math]\displaystyle{ O(1) }[/math] дополнительной памяти.

Устойчивость — равные элементы сохраняют порядок; достигается использованием строгого сравнения a[j] > a[j+1] (равные не меняются).

Адаптивность — ранний выход, если за проход не было обменов: массив уже отсортирован.

Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ j }[/math] — индекс пары; [math]\displaystyle{ \text{pass} }[/math] — номер прохода; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Пузырёк — вероятно, самый простой алгоритм сортировки: два вложенных цикла и обмен соседей. Его легко объяснить и запомнить, но он же и самый неэффективный по числу обменов: каждый крупный элемент продвигается вправо ровно на одну позицию за проход, а обмен выполняется на каждом шаге. Поэтому на реальных данных он уступает и вставкам, и выбору при той же асимптотике [math]\displaystyle{ O(n^2) }[/math] (см. рис. 6).

Идея в одном абзаце: идём по массиву и «выталкиваем» большой элемент вправо, повторяя проходы и сужая их границу. Если за проход обменов не было — сортировать больше нечего, можно остановиться (см. рис. 2). Это делает алгоритм адаптивным на почти отсортированных данных — единственное, где пузырёк может быть полезен.

Рис. 1. Сравниваем соседние пары; больший «всплывает» вправо, максимум доходит до конца.

Рис. 2. Флаг раннего выхода превращает пузырёк в адаптивный: отсортированный вход — [math]\displaystyle{ n-1 }[/math] сравнений.

Устройство

Обычно используется четырёхшаговая структура: внешний цикл по проходам, внутренний — по парам, сравнение и обмен. Граница внутреннего цикла уменьшается на 1 за проход (см. рис. 1 и рис. 3).

Рис. 3. Один проход: диапазон [math]\displaystyle{ j = 0 \dots n-2-\text{pass} }[/math]; максимум уходит вправо.

Две стандартные оптимизации:

• Флаг обмена — если проход не сделал ни одного обмена, массив отсортирован (ранний выход). Это делает алгоритм адаптивным: [math]\displaystyle{ n-1 }[/math] сравнений на отсортированном входе.
• Последний обмен — запоминаем индекс последнего обмена; всё правее него уже на своих местах, поэтому следующий проход можно сократить до этой точки (а не на фиксированную единицу).

Операции и алгоритмы

Операция: Bubble-Sort (базовая)

Идея. Сравниваем соседние пары; если пара не по порядку — меняем; так за проход максимум уходит в конец.

Пошаговое описание:

1. Для pass от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n-2 }[/math]:
2. Для j от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n-2-\text{pass} }[/math]: если a[j] > a[j+1], обменять.

Инвариант. Перед проходом pass последние pass элементов отсортированы и не меньше всех остальных (это pass наибольших элементов).

Алгоритм Bubble-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: после прохода k a[n−k..n−1] — k наибольших, отсортированы
Сложность: n(n−1)/2 сравнений всегда; O(1) памяти

1  for pass ← 0 to n − 2
2      for j ← 0 to n − 2 − pass
3          if a[j] > a[j + 1]        # строгое > → устойчивость
4              swap(a[j], a[j + 1])

Разбор. [5,1,4,2,8] (см. рис. 4): проход 1 даёт [1,4,2,5,8], проход 2 — [1,2,4,5,8], проход 3 — без обменов (стоп при оптимизации).

Сложность. Сравнений ровно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]; обменов до [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]; память [math]\displaystyle{ O(1) }[/math].

Крайние случаи. Отсортированный массив без флага — всё равно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] сравнений; [math]\displaystyle{ n \le 1 }[/math] — ничего.

Операция: оптимизированная версия (флаг + последний обмен)

Алгоритм Bubble-Sort-Opt(a)
1  end ← n − 1
2  while end > 0
3      lastSwap ← 0
4      for j ← 0 to end − 1
5          if a[j] > a[j + 1]
6              swap(a[j], a[j + 1])
7              lastSwap ← j
8      end ← lastSwap              # если обменов не было, lastSwap = 0 → выход

Разбор. Отсортированный вход: один проход, lastSwap = 0 → end = 0 → стоп, [math]\displaystyle{ n-1 }[/math] сравнений.

Сложность. Лучший [math]\displaystyle{ \Theta(n) }[/math]; средний/худший [math]\displaystyle{ \Theta(n^2) }[/math]. Обменов столько же, сколько в базовой (оптимизации сокращают сравнения/проходы, не число обменов).

Крайние случаи. Полностью обратный массив — end уменьшается на 1 за проход, [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] сравнений и обменов.

Рис. 4. Проходы, сужение границы и досрочный выход по отсутствию обменов.

Операция: шейкерная сортировка (cocktail shaker)

Идея. Чередуем проходы вперёд и назад: вперёд максимум уходит вправо, назад минимум — влево (см. рис. 5).

Алгоритм Cocktail-Sort(a)
1  lo ← 0 ; hi ← n − 1
2  while lo < hi
3      for j ← lo to hi − 1: if a[j] > a[j+1]: swap(a[j], a[j+1])
4      hi ← hi − 1
5      for j ← hi downto lo + 1: if a[j−1] > a[j]: swap(a[j−1], a[j])
6      lo ← lo + 1

Сложность. Та же [math]\displaystyle{ \Theta(n^2) }[/math]; на данных «беспорядочных по краям» быстрее обычного пузырька.

Крайние случаи. Почти отсортированные данные с «большим» в начале и «маленьким» в конце — шейкер заметно эффективнее одностороннего.

Рис. 5. Проходы в обе стороны; минимум и максимум ставятся на место за круг.

Вариант: comb sort (кратко)

Если сравнивать не соседей, а элементы с шагом [math]\displaystyle{ h \gt 1 }[/math], уменьшая его (например, деля на 1.3), сортировка становится быстрее — это comb sort. Она устраняет «черепах» (мелких элементов в конце) и родственна сортировке Шелла; при шаге 1 превращается в обычный пузырёк.

Сводная таблица сложности

Вариант	Лучший	Средний	Худший	Обменов	Память
Базовая	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	до [math]\displaystyle{ n^2/2 }[/math]	[math]\displaystyle{ O(1) }[/math]
С флагом/последним обменом	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	до [math]\displaystyle{ n^2/2 }[/math]	[math]\displaystyle{ O(1) }[/math]
Шейкерная	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	до [math]\displaystyle{ n^2/2 }[/math]	[math]\displaystyle{ O(1) }[/math]
Comb sort	[math]\displaystyle{ \approx n\log n }[/math] эмпир.	[math]\displaystyle{ \approx n^{1.3} }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	—	[math]\displaystyle{ O(1) }[/math]

Оговорка: оптимизации сокращают число проходов/сравнений на «почти отсортированных» данных, но не меняют класс [math]\displaystyle{ O(n^2) }[/math] и не уменьшают число обменов на случайном входе.

Трассировка примера

a = [5, 1, 4, 2, 8] (см. рис. 4).

Проход	Обменов	Массив после	Граница
старт	—	5 1 4 2 8	4
1	3	1 4 2 5 8	3
2	1	1 2 4 5 8	1
3	0	1 2 4 5 8	стоп (флаг)

Разбор прохода 1 (диапазон [math]\displaystyle{ j = 0..3 }[/math]): [math]\displaystyle{ (5,1) }[/math] → обмен; [math]\displaystyle{ (5,4) }[/math] → обмен; [math]\displaystyle{ (5,2) }[/math] → обмен; [math]\displaystyle{ (5,8) }[/math] — без обмена → 1 4 2 5 8. Всего сравнений: [math]\displaystyle{ 4+3+2 = 9 }[/math]. На проходе 3 обменов нет → сортировка завершается по флагу. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность (инвариант)

Инвариант. Перед проходом [math]\displaystyle{ k }[/math] последние [math]\displaystyle{ k }[/math] элементов массива отсортированы и не меньше всех остальных.

База. [math]\displaystyle{ k = 0 }[/math]: хвост пуст — верно.

Сохранение. При проходе [math]\displaystyle{ k }[/math] (граница [math]\displaystyle{ n-1-k }[/math]) максимум среди [math]\displaystyle{ a[0..n-1-k] }[/math] «всплывает» до позиции [math]\displaystyle{ n-1-k }[/math]: при каждом сравнении больший сдвигается вправо, поэтому после полного прохода этот максимум стоит в [math]\displaystyle{ a[n-1-k] }[/math], а он не меньше хвоста (все прочие элементы не больше него). Значит, хвост вырос на один отсортированный максимум. Инвариант сохранён.

Завершение. После прохода [math]\displaystyle{ n-2 }[/math] отсортирован весь массив (хвост размером [math]\displaystyle{ n-1 }[/math]). При использовании флага возможен более ранний выход: отсутствие обменов означает, что порядок уже неубывающий. [math]\displaystyle{ \square }[/math]

Точные оценки

Сравнений в базовой версии: [math]\displaystyle{ \sum_{k=0}^{n-2}(n-1-k) = \frac{n(n-1)}{2} }[/math] — независимо от входа. Обменов: не более одного на сравнение, до [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] (ровно столько на обратном массиве). С флагом лучший случай — [math]\displaystyle{ n-1 }[/math] сравнений и 0 обменов.

Связь с инверсиями. Каждый обмен соседних элементов устраняет ровно одну инверсию и не создаёт новых, поэтому общее число обменов равно числу инверсий исходного массива. Отсюда: обратный массив даёт ровно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] обменов, отсортированный — ноль. Это же объясняет, почему на «почти отсортированных» данных пузырёк с флагом работает за [math]\displaystyle{ O(n) }[/math].

Устойчивость

При сравнении используется строгое a[j] > a[j+1]; равные элементы не меняются местами, поэтому порядок равных сохраняется — сортировка устойчива.

Сравнение с альтернативами

Алгоритм	Лучший / худший	Обменов	Устойчив	Ниша
Пузырёк	[math]\displaystyle{ n }[/math] (флаг) / [math]\displaystyle{ n^2 }[/math]	до [math]\displaystyle{ n^2/2 }[/math]	да	обучение, детект сортировки
Вставками	[math]\displaystyle{ n }[/math] / [math]\displaystyle{ n^2 }[/math]	[math]\displaystyle{ O(n+\text{inv}) }[/math]	да	почти всегда лучше пузырька
Выбором	[math]\displaystyle{ n^2 }[/math] / [math]\displaystyle{ n^2 }[/math]	[math]\displaystyle{ \le n-1 }[/math]	нет	дорогая запись
Шелл	[math]\displaystyle{ n }[/math] / [math]\displaystyle{ \approx n^{1.3} }[/math]	—	нет	средние массивы
Пирамидальная	[math]\displaystyle{ n\log n }[/math] / [math]\displaystyle{ n\log n }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	нет	гарантия, [math]\displaystyle{ O(1) }[/math] памяти

Рис. 6. Пузырёк: та же асимптотика, но больше обменов — почти всегда худший выбор.

Вердикт. Замените пузырёк на вставки (обычно быстрее и меньше перемещений) или на выбор (при дорогой записи). Пузырёк держите только для обучения и как источник идеи «флаг адаптивности» и comb sort.

Где применяется

1. Обучение. Самый наглядный пример обменной сортировки с ясным инвариантом «отсортированный хвост» и демонстрацией адаптивности [1][2].

1. Проверка «уже отсортировано». С флагом за один проход определяет, отсортирован ли массив ([math]\displaystyle{ n-1 }[/math] сравнение, 0 обменов) — дешёвая проверка почти готовых данных [3].

1. Comb sort. Обобщение пузырька на шаг [math]\displaystyle{ \gt 1 }[/math] — практичный [math]\displaystyle{ O(n^{1.3}) }[/math]-эмпирический алгоритм, родственный Шеллу [4].

1. Встраиваемые и учебные реализации. Изредка используется на крошечных массивах из-за предельной простоты; обычно уступает вставкам [3].

Рис. 7. Пузырёк: обучение, детект сортировки, мост к comb sort.

Историческая справка

Обменные сортировки известны с первых лет вычислительной техники; сам термин «bubble sort» закрепил Дональд Кнут в The Art of Computer Programming, т. 3 (§5.2.2), где разобраны его инварианты, число сравнений и обменов и отмечена низкая эффективность [2]. Пузырёк часто приписывают ранним работам по сортировке, но как «рабочий» алгоритм он был вытеснен вставками и выбором ещё до появления быстрых [math]\displaystyle{ O(n\log n) }[/math]-методов.

Обобщение на шаг — comb sort — описали Влодзимеж Добосевич (Dobosiewicz, 1980) и позже исследовали Лейси и Бокс (1991), назвавшие его comb sort и подобравшие коэффициент уменьшения шага [math]\displaystyle{ \approx 1.3 }[/math] [4]. Шейкерная сортировка (cocktail shaker sort) — прямой двунаправленный вариант пузырька.

Типичные ошибки и подводные камни

• Нет флага — нет адаптивности. Без раннего выхода пузырёк делает [math]\displaystyle{ n^2/2 }[/math] сравнений даже на отсортированном массиве.
• Неверная граница прохода. j < n-1-pass (а не n-1), иначе лишние сравнения или выход за массив.
• Неустойчивость при >=. Замена сравнения на a[j] >= a[j+1] ломает устойчивость.
• Много обменов. До [math]\displaystyle{ n^2/2 }[/math] обменов против [math]\displaystyle{ O(n) }[/math] у выбора — главный минус на практике.
• lastSwap как индекс vs позиция. Классическая ошибка: сохранять j+1 и не сужать границу (см. сноску к optimized-версии).
• Применение на больших массивах. [math]\displaystyle{ O(n^2) }[/math] неприемлемо; используйте [math]\displaystyle{ O(n\log n) }[/math]-алгоритмы.
• Путаница с comb sort. Comb sort — не «пузырёк», а его обобщение с шагом; при шаге 1 совпадает с ним.
• Шейкер как «ускорение». Асимптотика та же; выигрыш лишь на специальных входах.
• Сравнение «пузырёк быстрее на почти отсортированных». Вставки в этом режиме минимум не хуже, а обычно лучше (меньше записей).
• Диагностический вывод. Частая причина «тормозов» в учебном коде — вывод массива внутри вложенных циклов, а не сам алгоритм.

Задачи для практики

1. Базовая версия. Реализуйте пузырёк и посчитайте сравнения/обмены. Подсказка: сужающаяся граница.

1. Флаг. Добавьте ранний выход и покажите, что на отсортированном массиве [math]\displaystyle{ n-1 }[/math] сравнений. Подсказка: флаг обмена.

1. Последний обмен. Реализуйте сужение по последнему обмену; сравните число проходов. Подсказка: end = lastSwap.

1. Шейкер. Реализуйте cocktail shaker и сравните на входе с «большим в начале, маленьким в конце». Подсказка: проходы в обе стороны.

1. Обмены. Докажите, что обменов не больше, чем сравнений, и постройте вход с ровно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] обменами. Подсказка: обратный массив.

1. Устойчивость. Приведите контрпример для >= и проверьте, что при > порядок равных сохраняется. Подсказка: пары (ключ, метка).

1. Comb sort. Реализуйте comb sort с шагом, делящимся на 1.3, и сравните с пузырьком. Подсказка: при шаге 1 — обычный пузырёк.

1. Сравнение. Для [math]\displaystyle{ n = 1000 }[/math] сравните сравнения и обмены пузырька, вставок и выбора. Подсказка: вставки адаптивны, выбор экономит обмены.

Связанные темы

• Сортировки — обзор и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
• Сортировка вставками — почти всегда лучшая замена пузырька.
• Сортировка выбором — минимум записей.
• Сортировка Шелла — родственник через comb sort.
• Асимптотическая сложность — лучший/средний/худший случаи.

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Задача 2-2 (bubble sort; инвариант, число инверсий).
2. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.2 (bubble sort; анализ).
3. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts).
4. Dobosiewicz W. A More Efficient Variation of Bubble Sort // Information Processing Letters. — 1980; Lacey S., Box R. A Fast, Easy Sort // Dr. Dobb's Journal. — 1991 (comb sort).
5. Wikipedia: Bubble sort. URL: https://en.wikipedia.org/wiki/Bubble_sort .