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

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 и шейкерной сортировки.

Свойство	Значение
Класс	Сортировка сравнением; обменная (sorting by exchange); на месте
Изобретение	E. H. Friend, 1956 — первое описание; название «bubble sort» — K. E. Iverson
Идея	Сравнение соседних пар и обмен «неправильных»
Лучший случай	[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] элементов стоят на своих местах, поэтому граница прохода сужается на единицу.

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

Кролики и черепахи (rabbits and turtles). Крупные элементы («кролики») за один проход пузырька могут уйти далеко вправо, а мелкие («черепахи») сдвигаются влево не более чем на одну позицию за проход — отсюда долгая сортировка входов с маленьким элементом в конце (см. рис. 1).

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

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

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

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

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

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

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

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

Рис. 1. За один проход 5 сдвинулся вправо на три позиции, а 2 — влево только на одну: «кролики» бегут, «черепахи» ползут.

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

Устройство

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

Рис. 3. Один проход: диапазон [math]\displaystyle{ j = 0 \dots n-2-\mathit{pass} }[/math]; максимум прохода занимает последнюю ячейку; граница следующего прохода уменьшается.

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

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

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

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

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

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

Для pass от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n-2 }[/math]:
Для j от [math]\displaystyle{ 0 }[/math] до [math]\displaystyle{ n-2-\mathit{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) памяти
Корректность: после прохода k хвост a[n−k..n−1] отсортирован;
             после прохода n−2 отсортирован весь массив

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 обменов не делает — с флагом сортировка здесь останавливается (базовая версия сделала бы ещё проход 4).

Сложность. Сравнений ровно [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] — ничего.

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

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

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

end ← n − 1.
lastSwap ← 0; пройти j от [math]\displaystyle{ 0 }[/math] до end − 1: при a[j] > a[j+1] обменять и записать lastSwap ← j.
end ← lastSwap; если end = 0, сортировка завершена.
Иначе повторить с шага 2.

Инвариант. К началу прохода a[end+1..n−1] отсортировано, стоит на своих местах и не меньше a[0..end] (при end = n−1 хвост пуст).

Алгоритм Bubble-Sort-Opt(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: a[end+1..n−1] отсортировано и не меньше a[0..end]
Сложность: лучший Θ(n), средний/худший Θ(n²); O(1) памяти
Корректность: правее lastSwap обменов не было, значит, суффикс уже отсортирован;
             lastSwap = 0 → массив отсортирован

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] сравнений. На [5,1,4,2,8] версия с lastSwap делает 7 сравнений ([math]\displaystyle{ 4+2+1 }[/math]) вместо 9 у версии с флагом и фиксированным сужением границы; обменов в обоих случаях 4 (см. рис. 4).

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

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

Рис. 4. Трассировка [math]\displaystyle{ [5, 1, 4, 2, 8] }[/math] для версии с флагом: границы [math]\displaystyle{ 4 \to 3 \to 2 }[/math], 9 сравнений, 4 обмена; проход без обменов останавливает сортировку.

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

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

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

lo ← 0, hi ← n − 1.
Проход вперёд по j = lo..hi−1: максимум поднимается к hi; затем hi ← hi − 1.
Проход назад по j = hi..lo+1: минимум опускается к lo; затем lo ← lo + 1.
Повторять, пока lo < hi.

Инвариант. К началу круга a[0..lo−1] — lo наименьших элементов по порядку, a[hi+1..n−1] — n−1−hi наибольших по порядку; сортируемая часть — a[lo..hi].

Алгоритм Cocktail-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: a[0..lo−1] и a[hi+1..n−1] отсортированы и стоят на своих местах
Сложность: Θ(n²) сравнений в худшем случае и в лучшем без флага; с флагом лучший Θ(n);
           O(1) памяти
Корректность: за круг максимум встаёт в hi, минимум — в lo; границы сужаются,
             цикл конечен; при lo ≥ hi остаётся не более одного элемента

1  lo ← 0 ; hi ← n − 1
2  while lo < hi
3      for j ← lo to hi − 1
4          if a[j] > a[j + 1]
5              swap(a[j], a[j + 1])
6      hi ← hi − 1
7      for j ← hi downto lo + 1
8          if a[j − 1] > a[j]
9              swap(a[j − 1], a[j])
10     lo ← lo + 1

Пример. [5,1,4,2,8] (см. рис. 5): проход вперёд даёт 1 4 2 5 8 (8 на месте), после чего hi уменьшается; проход назад — 1 2 4 5 8 (1 на месте), после чего lo растёт; за один круг встали и минимум, и максимум.

Сложность. Та же [math]\displaystyle{ \Theta(n^2) }[/math] в худшем случае: каждый круг сокращает диапазон на 2, поэтому сравнений порядка [math]\displaystyle{ n^2 }[/math]; на данных «беспорядочных по краям» шейкер быстрее обычного пузырька. С флагом раннего выхода лучший случай [math]\displaystyle{ \Theta(n) }[/math], без флага — [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{ \frac{n(n-1)}{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{ \frac{n(n-1)}{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{ \Theta(n^2) }[/math]	до [math]\displaystyle{ \frac{n(n-1)}{2} }[/math]	[math]\displaystyle{ O(1) }[/math]
Comb sort	[math]\displaystyle{ \Theta(n\log n) }[/math]	[math]\displaystyle{ \approx n^{1.3} }[/math] (эмпирически)	[math]\displaystyle{ O(n^2) }[/math]	—	[math]\displaystyle{ O(1) }[/math]

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

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

a = [5, 1, 4, 2, 8] (см. рис. 4). Трассируется версия с флагом раннего выхода: граница end уменьшается на 1 за проход (сужение по lastSwap разобрано отдельно).

Проход	Обменов	Массив после	Граница
старт	—	`5 1 4 2 8`	4
1	3	`1 4 2 5 8`	3
2	1	`1 2 4 5 8` (5 и 8 на месте)	2
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 обменов нет → сортировка завершается по флагу. Числа получены прямым пересчётом по шагам трассировки; базовый псевдокод на этом входе даёт 10 сравнений, а версия с lastSwap — 7 ([math]\displaystyle{ 4+2+1 }[/math]) при тех же 4 обменах.

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

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

Инвариант. Перед проходом [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{ [2,3,\dots,n,1] }[/math] имеет всего [math]\displaystyle{ n-1 }[/math] инверсию, однако «черепаха» 1 сдвигается влево лишь на одну позицию за проход, поэтому нужны [math]\displaystyle{ n-1 }[/math] проходов и [math]\displaystyle{ \Theta(n^2) }[/math] сравнений. Время [math]\displaystyle{ O(n) }[/math] получается только тогда, когда все элементы уже близко к своим местам и хватает одного–двух проходов.

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

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

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

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

Примечание: оценка [math]\displaystyle{ \approx n^{1.3} }[/math] для сортировки Шелла — эмпирическая средняя, а не худший случай; худший случай зависит от выбранной последовательности шагов.

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

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

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

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

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

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

Очень малые массивы. На массивах из одного–двух элементов разницы нет; при очень малых [math]\displaystyle{ n }[/math] решает простота кода, но и здесь обычно предпочитают вставки [3].

Все четыре ниши — на рис. 7.

Рис. 7. Четыре ниши пузырька: обучение, детект сортированности, мост к comb sort, очень малые массивы.

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

Первое описание алгоритма дал Эдвард Х. Френд (Edward H. Friend) в работе «Sorting on Electronic Computer Systems» (Journal of the ACM, 1956) — как «sorting exchange algorithm» [6]. Название «bubble sort» связывают с Кеннетом Айверсоном (Kenneth E. Iverson) [7]. Дональд Кнут разобрал алгоритм в The Art of Computer Programming, т. 3, §5.2.2: там исследованы его инварианты, число сравнений и обменов и отмечена низкая эффективность [2].

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

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

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

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

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

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

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

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

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

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

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

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

Ответы.

[math]\displaystyle{ \frac{n(n-1)}{2} }[/math] сравнений; на [5,1,4,2,8] — 10 сравнений и 4 обмена.
Для [math]\displaystyle{ n = 10\,000 }[/math]: 9999 сравнений, 0 обменов, один проход.
[5,1,4,2,8]: 7 сравнений ([math]\displaystyle{ 4+2+1 }[/math]) против 9 у версии с флагом и фиксированным сужением.
[2,3,…,n,1]: пузырёк с флагом — [math]\displaystyle{ n-1 }[/math] проходов и [math]\displaystyle{ \approx \frac{n^2}{2} }[/math] сравнений; шейкер сортирует такой вход за один круг ([math]\displaystyle{ \approx 2n }[/math] сравнений: [math]\displaystyle{ n-1 }[/math] вперёд и [math]\displaystyle{ n-2 }[/math] назад), но без флага продолжает круги и делает [math]\displaystyle{ \approx \frac{n^2}{2} }[/math] сравнений (45 при [math]\displaystyle{ n = 10 }[/math]); с флагом он останавливается на первом проходе без обменов — это уже второй круг, а не первый.
Обмен возможен только при сравнении, поэтому обменов не больше; на обратном массиве каждая пара — инверсия, ровно [math]\displaystyle{ \frac{n(n-1)}{2} }[/math].
Пары (1,a), (1,b): при >= обмен меняет метки местами, при > порядок сохраняется.
При шаге 1 comb sort совпадает с пузырьком с флагом; «черепаха» в конце устраняется первым проходом с большим шагом.
Для [math]\displaystyle{ n = 1000 }[/math]: пузырёк и выбор — ровно 499 500 сравнений; у выбора [math]\displaystyle{ \le 999 }[/math] обменов; вставки в среднем — [math]\displaystyle{ \approx \frac{n^2}{4} }[/math] сравнений и перемещений, на отсортированном — [math]\displaystyle{ n-1 }[/math].

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

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

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Problem 2-2 (bubble sort; инвариант, число инверсий).
Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.2 (Sorting by Exchanging; анализ).
Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts).
Dobosiewicz W., Borowy A. An efficient variation of bubble sort // Information Processing Letters. — 1980. — Vol. 11, No. 1. — P. 5–6.
Lacey S., Box R. A Fast, Easy Sort // Byte. — 1991. — Vol. 16, No. 4. — P. 315–318, 320.
Friend E. H. Sorting on Electronic Computer Systems // Journal of the ACM. — 1956. — Vol. 3, No. 3. — P. 134–168.
Wikipedia: Bubble sort. URL: https://en.wikipedia.org/wiki/Bubble_sort; Comb sort. URL: https://en.wikipedia.org/wiki/Comb_sort.

Поиск

Навигация

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

Содержание

TL;DR

Определения

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

Устройство

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники