Сортировка пузырьком: различия между версиями

Версия 16:33, 26 октября 2026

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.

Поиск

Навигация

Сортировка пузырьком: различия между версиями

Версия 16:33, 26 октября 2026

Содержание

TL;DR

Определения

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

Устройство

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники

@@ Строка 1: / Строка 1: @@
 == TL;DR ==
-'''Сортировка пузырьком''' (bubble sort) многократно проходит по массиву, сравнивая '''соседние''' элементы и меняя их, если они стоят не по порядку; за каждый проход наибольший элемент «всплывает» в конец рассматриваемой части. Алгоритм работает '''на месте''' (<math>O(1)</math> памяти) и '''устойчив''', а с '''флагом раннего выхода''' становится '''адаптивным''': на уже отсортированном массиве делает <math>n-1</math> сравнение и завершается. Но в среднем и худшем случаях — <math>\Theta(n^2)</math> сравнений и до <math>\frac{n(n-1)}{2}</math> '''обменов''', что делает его самым «затратным» из элементарных сортировок. Поэтому на практике пузырёк почти не используется: он ценен как '''учебный пример''' инвариантов и адаптивности, а также как основа для '''comb sort''' и '''шейкерной''' сортировки.
+'''Сортировка пузырьком''' (bubble sort) многократно проходит по массиву, сравнивая '''соседние''' элементы и меняя их, если они стоят не по порядку; за каждый проход наибольший элемент «всплывает» в конец рассматриваемой части. Алгоритм работает '''на месте''' (<math>O(1)</math> памяти) и '''устойчив''', а с '''флагом раннего выхода''' становится '''адаптивным''': на уже отсортированном массиве делает <math>n-1</math> сравнений и завершается. Но в среднем и худшем случаях — <math>\Theta(n^2)</math> сравнений и до <math>\frac{n(n-1)}{2}</math> '''обменов''', что делает его самым затратным по числу записей среди элементарных сортировок. Поэтому на практике пузырёк почти не используется: он ценен как '''учебный пример''' инвариантов и адаптивности, а также как основа для '''comb sort''' и '''шейкерной''' сортировки.
 {| class="wikitable"
@@ Строка 7: / Строка 7: @@
 ! Свойство !! Значение
 |-
-| Класс || Сортировка сравнением; обменная (exchange sort); на месте
+| Класс || Сортировка сравнением; обменная (sorting by exchange); на месте
+|-
+| Изобретение || E. H. Friend, 1956 — первое описание; название «bubble sort» — K. E. Iverson
 |-
 | Идея || Сравнение соседних пар и обмен «неправильных»
@@ Строка 15: / Строка 17: @@
 | Средний / худший || <math>\Theta(n^2)</math>
 |-
-| Обменов || до <math>\frac{n(n-1)}{2}</math> (много!)
+| Обменов || до <math>\frac{n(n-1)}{2}</math> (много)
 |-
 | Память || <math>O(1)</math>
@@ Строка 36: / Строка 38: @@
 '''Проход (pass).''' Один линейный проход по текущей части массива. После <math>k</math>-го прохода последние <math>k</math> элементов стоят на своих местах, поэтому граница прохода сужается на единицу.
-'''Обменный алгоритм (exchange sort).''' Класс сортировок, переставляющих элементы обменом соседних; пузырёк — наиболее известный представитель (иногда его зовут ''sinking sort'' — «сортировка погружением», если смотреть на всплывающий вниз максимум).
+'''Обменные сортировки (sorting by exchange)''' — класс алгоритмов, переставляющих элементы обменом соседних; пузырёк — наиболее известный представитель класса, а не отдельный «обменный алгоритм» (иногда его зовут ''sinking sort'': большие элементы «тонут» вниз).
+'''Кролики и черепахи (rabbits and turtles).''' Крупные элементы («кролики») за один проход пузырька могут уйти далеко вправо, а мелкие («черепахи») сдвигаются влево не более чем на одну позицию за проход — отсюда долгая сортировка входов с маленьким элементом в конце (см. рис. 1).
 '''На месте (in-place)''' — <math>O(1)</math> дополнительной памяти.
@@ Строка 44: / Строка 48: @@
 '''Адаптивность''' — ранний выход, если за проход '''не было обменов''': массив уже отсортирован.
-'''Обозначения.''' <math>n</math> — длина массива; <math>j</math> — индекс пары; <math>\text{pass}</math> — номер прохода; <math>\log</math> — двоичный.
+'''Обозначения.''' <math>n</math> — длина массива; <math>j</math> — индекс пары; <code>pass</code> — номер прохода; <math>\log</math> — двоичный.
 == Мотивация и интуиция ==
-Пузырёк — вероятно, '''самый простой''' алгоритм сортировки: два вложенных цикла и обмен соседей. Его легко объяснить и запомнить, но он же и самый неэффективный по числу обменов: каждый крупный элемент продвигается вправо ровно '''на одну позицию за проход''', а обмен выполняется на каждом шаге. Поэтому на реальных данных он уступает и [[Сортировка вставками\|вставкам]], и [[Сортировка выбором\|выбору]] при той же асимптотике <math>O(n^2)</math> (см. рис. 6).
+Пузырёк — вероятно, '''самый простой''' алгоритм сортировки: два вложенных цикла и обмен соседей. Его легко объяснить и запомнить, но на реальных данных он уступает и [[Сортировка вставками|вставкам]], и [[Сортировка выбором|выбору]] при той же асимптотике <math>O(n^2)</math> (см. рис. 6). Обмен выполняется только там, где пара стоит не по порядку, но каждая перестановка — это две записи: пузырёк делает столько же обменов, сколько инверсий во входе, и проигрывает по числу записей/перемещений.
+Ключевая асимметрия видна на рис. 1: '''крупные элементы («кролики») за один проход уходят далеко вправо''', а '''мелкие («черепахи») сдвигаются влево не более чем на одну позицию за проход'''. Поэтому вход с одним маленьким элементом в конце сортируется долго: этот элемент ползёт к началу по одной позиции за проход.
-Идея в одном абзаце: '''идём по массиву и «выталкиваем» большой элемент вправо''', повторяя проходы и сужая их границу. Если за проход обменов не было — сортировать больше нечего, можно остановиться (см. рис. 2). Это делает алгоритм адаптивным на почти отсортированных данных — единственное, где пузырёк может быть полезен.
+Идея в одном абзаце: '''идём по массиву и «выталкиваем» большой элемент вправо''', повторяя проходы и сужая их границу. Если за проход обменов не было — сортировать больше нечего, можно остановиться (см. рис. 2). Это делает алгоритм адаптивным на почти отсортированных данных — одна из немногих ситуаций, где пузырёк бывает полезен.
-[[Файл:bs-01-idea.svg|frame|none|700px|Рис. 1. Сравниваем соседние пары; больший «всплывает» вправо, максимум доходит до конца.]]
+[[Файл:bs-01-idea.svg|frame|none|700px|Рис. 1. За один проход 5 сдвинулся вправо на три позиции, а 2 — влево только на одну: «кролики» бегут, «черепахи» ползут.]]
-[[Файл:bs-02-adaptive.svg|frame|none|700px|Рис. 2. Флаг раннего выхода превращает пузырёк в адаптивный: отсортированный вход — <math>n-1</math> сравнений.]]
+[[Файл:bs-02-adaptive.svg|frame|none|700px|Рис. 2. Флаг раннего выхода делает пузырёк адаптивным: отсортированный вход — <math>n-1</math> сравнений; сужение по последнему обмену сокращает и число проходов.]]
 == Устройство ==
@@ Строка 60: / Строка 66: @@
 Обычно используется четырёхшаговая структура: внешний цикл по проходам, внутренний — по парам, сравнение и обмен. Граница внутреннего цикла уменьшается на 1 за проход (см. рис. 1 и рис. 3).
-[[Файл:bs-03-pass.svg|frame|none|700px|Рис. 3. Один проход: диапазон <math>j = 0 \dots n-2-\text{pass}</math>; максимум уходит вправо.]]
+[[Файл:bs-03-pass.svg|frame|none|700px|Рис. 3. Один проход: диапазон <math>j = 0 \dots n-2-\mathit{pass}</math>; максимум прохода занимает последнюю ячейку; граница следующего прохода уменьшается.]]
 Две стандартные оптимизации:
@@ Строка 76: / Строка 82: @@
 # Для <code>pass</code> от <math>0</math> до <math>n-2</math>:
-# Для <code>j</code> от <math>0</math> до <math>n-2-\text{pass}</math>: если <code>a[j] &gt; a[j+1]</code>, обменять.
+# Для <code>j</code> от <math>0</math> до <math>n-2-\mathit{pass}</math>: если <code>a[j] &gt; a[j+1]</code>, обменять.
 '''Инвариант.''' Перед проходом <code>pass</code> последние <code>pass</code> элементов отсортированы и не меньше всех остальных (это <code>pass</code> наибольших элементов).
@@ Строка 86: / Строка 92: @@
 Инвариант: после прохода k a[n−k..n−1] — k наибольших, отсортированы
 Сложность: n(n−1)/2 сравнений всегда; O(1) памяти
+Корректность: после прохода k хвост a[n−k..n−1] отсортирован;
+             после прохода n−2 отсортирован весь массив
   for pass ← 0 to n − 2
@@ Строка 93: / Строка 101: @@
 </syntaxhighlight>
-'''Разбор.''' <code>[5,1,4,2,8]</code> (см. рис. 4): проход 1 даёт <code>[1,4,2,5,8]</code>, проход 2 — <code>[1,2,4,5,8]</code>, проход 3 — без обменов (стоп при оптимизации).
+'''Разбор.''' <code>[5,1,4,2,8]</code> (см. рис. 4): проход 1 даёт <code>[1,4,2,5,8]</code>, проход 2 — <code>[1,2,4,5,8]</code>, проход 3 обменов не делает — с флагом сортировка здесь останавливается (базовая версия сделала бы ещё проход 4).
 '''Сложность.''' Сравнений ровно <math>\frac{n(n-1)}{2}</math>; обменов до <math>\frac{n(n-1)}{2}</math>; память <math>O(1)</math>.
@@ Строка 100: / Строка 108: @@
 === Операция: оптимизированная версия (флаг + последний обмен) ===
+'''Идея.''' Запоминаем индекс последнего обмена: всё правее него уже стоит на своих местах, поэтому следующий проход можно закончить раньше. Если обменов не было вовсе, массив отсортирован.
+'''Пошаговое описание:'''
+# <code>end ← n − 1</code>.
+# <code>lastSwap ← 0</code>; пройти <code>j</code> от <math>0</math> до <code>end − 1</code>: при <code>a[j] &gt; a[j+1]</code> обменять и записать <code>lastSwap ← j</code>.
+# <code>end ← lastSwap</code>; если <code>end = 0</code>, сортировка завершена.
+# Иначе повторить с шага 2.
+'''Инвариант.''' К началу прохода <code>a[end+1..n−1]</code> отсортировано, стоит на своих местах и не меньше <code>a[0..end]</code> (при <code>end = n−1</code> хвост пуст).
 <syntaxhighlight lang="text">
 Алгоритм Bubble-Sort-Opt(a)
+Вход:  массив a[0..n−1]
+Выход: a отсортирован по неубыванию
+Инвариант: a[end+1..n−1] отсортировано и не меньше a[0..end]
+Сложность: лучший Θ(n), средний/худший Θ(n²); O(1) памяти
+Корректность: правее lastSwap обменов не было, значит, суффикс уже отсортирован;
+             lastSwap = 0 → массив отсортирован
   end ← n − 1
   while end > 0
@@ Строка 113: / Строка 139: @@
 </syntaxhighlight>
-'''Разбор.''' Отсортированный вход: один проход, <code>lastSwap = 0</code> → <code>end = 0</code> → стоп, <math>n-1</math> сравнений.
+'''Пример.''' Отсортированный вход: один проход, <code>lastSwap = 0</code> → <code>end = 0</code> → стоп, <math>n-1</math> сравнений. На <code>[5,1,4,2,8]</code> версия с <code>lastSwap</code> делает 7 сравнений (<math>4+2+1</math>) вместо 9 у версии с флагом и фиксированным сужением границы; обменов в обоих случаях 4 (см. рис. 4).
-'''Сложность.''' Лучший <math>\Theta(n)</math>; средний/худший <math>\Theta(n^2)</math>. Обменов столько же, сколько в базовой (оптимизации сокращают '''сравнения/проходы''', не число обменов).
+'''Сложность.''' Лучший <math>\Theta(n)</math>: на отсортированном входе один проход из <math>n-1</math> сравнений. Средний/худший <math>\Theta(n^2)</math> — как у базовой по числу проходов и сравнений; обменов столько же, сколько в базовой (оптимизации сокращают '''сравнения/проходы''', не число обменов).
 '''Крайние случаи.''' Полностью обратный массив — <code>end</code> уменьшается на 1 за проход, <math>\frac{n(n-1)}{2}</math> сравнений и обменов.
-[[Файл:bs-04-trace.svg|frame|none|700px|Рис. 4. Проходы, сужение границы и досрочный выход по отсутствию обменов.]]
+[[Файл:bs-04-trace.svg|frame|none|700px|Рис. 4. Трассировка <math>[5, 1, 4, 2, 8]</math> для версии с флагом: границы <math>4 \to 3 \to 2</math>, 9 сравнений, 4 обмена; проход без обменов останавливает сортировку.]]
 === Операция: шейкерная сортировка (cocktail shaker) ===
 '''Идея.''' Чередуем проходы вперёд и назад: вперёд максимум уходит вправо, назад минимум — влево (см. рис. 5).
+'''Пошаговое описание:'''
+# <code>lo ← 0</code>, <code>hi ← n − 1</code>.
+# Проход вперёд по <code>j = lo..hi−1</code>: максимум поднимается к <code>hi</code>; затем <code>hi ← hi − 1</code>.
+# Проход назад по <code>j = hi..lo+1</code>: минимум опускается к <code>lo</code>; затем <code>lo ← lo + 1</code>.
+# Повторять, пока <code>lo &lt; hi</code>.
+'''Инвариант.''' К началу круга <code>a[0..lo−1]</code> — <code>lo</code> наименьших элементов по порядку, <code>a[hi+1..n−1]</code> — <code>n−1−hi</code> наибольших по порядку; сортируемая часть — <code>a[lo..hi]</code>.
 <syntaxhighlight lang="text">
 Алгоритм 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 остаётся не более одного элемента
   lo ← 0 ; hi ← n − 1
   while lo < hi
-      for j ← lo to hi − 1: if a[j] > a[j+1]: swap(a[j], a[j+1])
+      for j ← lo to hi − 1
-     hi ← hi − 1
+          if a[j] > a[j + 1]
-     for j ← hi downto lo + 1: if a[j−1] > a[j]: swap(a[j−1], a[j])
+              swap(a[j], a[j + 1])
-      lo ← lo + 1
+     hi ← hi − 1
+     for j ← hi downto lo + 1
+          if a[j − 1] > a[j]
+              swap(a[j − 1], a[j])
+     lo ← lo + 1
 </syntaxhighlight>
-'''Сложность.''' Та же <math>\Theta(n^2)</math>; на данных «беспорядочных по краям» быстрее обычного пузырька.
+'''Пример.''' <code>[5,1,4,2,8]</code> (см. рис. 5): проход вперёд даёт <code>1 4 2 5 8</code> (8 на месте), после чего <code>hi</code> уменьшается; проход назад — <code>1 2 4 5 8</code> (1 на месте), после чего <code>lo</code> растёт; за один круг встали и минимум, и максимум.
+'''Сложность.''' Та же <math>\Theta(n^2)</math> в худшем случае: каждый круг сокращает диапазон на 2, поэтому сравнений порядка <math>n^2</math>; на данных «беспорядочных по краям» шейкер быстрее обычного пузырька. С флагом раннего выхода лучший случай <math>\Theta(n)</math>, без флага — <math>\Theta(n^2)</math>: в псевдокоде флага нет.
 '''Крайние случаи.''' Почти отсортированные данные с «большим» в начале и «маленьким» в конце — шейкер заметно эффективнее одностороннего.
-[[Файл:bs-05-cocktail.svg|frame|none|700px|Рис. 5. Проходы в обе стороны; минимум и максимум ставятся на место за круг.]]
+[[Файл:bs-05-cocktail.svg|frame|none|700px|Рис. 5. Проходы в обе стороны: за круг на место встают и минимум, и максимум.]]
 === Вариант: comb sort (кратко) ===
-Если сравнивать не соседей, а элементы с '''шагом''' <math>h > 1</math>, уменьшая его (например, деля на 1.3), сортировка становится быстрее — это '''comb sort'''. Она устраняет «черепах» (мелких элементов в конце) и родственна [[Сортировка шелла\|сортировке Шелла]]; при шаге 1 превращается в обычный пузырёк.
+Если сравнивать не соседей, а элементы с '''шагом''' <math>h > 1</math>, уменьшая его (например, деля на 1.3), сортировка становится быстрее — это '''comb sort'''. Она устраняет «черепах» (мелких элементов в конце) и родственна [[Сортировка Шелла|сортировке Шелла]]; при шаге 1 превращается в обычный пузырёк.
 == Сводная таблица сложности ==
@@ Строка 151: / Строка 200: @@
 ! Вариант !! Лучший !! Средний !! Худший !! Обменов !! Память
 |-
-| Базовая || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || до <math>n^2/2</math> || <math>O(1)</math>
+| Базовая || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || до <math>\frac{n(n-1)}{2}</math> || <math>O(1)</math>
 |-
-| С флагом/последним обменом || <math>\Theta(n)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || до <math>n^2/2</math> || <math>O(1)</math>
+| С флагом/последним обменом || <math>\Theta(n)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || до <math>\frac{n(n-1)}{2}</math> || <math>O(1)</math>
 |-
-| Шейкерная || <math>\Theta(n)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || до <math>n^2/2</math> || <math>O(1)</math>
+| Шейкерная || <math>\Theta(n)</math> с флагом; <math>\Theta(n^2)</math> без || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || до <math>\frac{n(n-1)}{2}</math> || <math>O(1)</math>
 |-
-| Comb sort || <math>\approx n\log n</math> эмпир. || <math>\approx n^{1.3}</math> || <math>\Theta(n^2)</math> || — || <math>O(1)</math>
+| Comb sort || <math>\Theta(n\log n)</math> || <math>\approx n^{1.3}</math> (эмпирически) || <math>O(n^2)</math> || — || <math>O(1)</math>
 |}
-Оговорка: оптимизации сокращают '''число проходов/сравнений''' на «почти отсортированных» данных, но не меняют класс <math>O(n^2)</math> и не уменьшают число обменов на случайном входе.
+Оговорка: оптимизации сокращают '''число проходов/сравнений''' на «почти отсортированных» данных, но не меняют класс <math>O(n^2)</math> и не уменьшают число обменов на случайном входе. Лучший случай <math>\Theta(n)</math> у шейкерной версии достигается только с флагом раннего выхода.
 == Трассировка примера ==
-<code>a = [5, 1, 4, 2, 8]</code> (см. рис. 4).
+<code>a = [5, 1, 4, 2, 8]</code> (см. рис. 4). Трассируется версия с флагом раннего выхода: граница <code>end</code> уменьшается на 1 за проход (сужение по <code>lastSwap</code> разобрано отдельно).
 {| class="wikitable"
@@ Строка 174: / Строка 223: @@
 | 1 || 3 || <code>1 4 2 5 8</code> || 3
 |-
-| 2 || 1 || <code>1 2 4 5 8</code> || 1
+| 2 || 1 || <code>1 2 4 5 8</code> (5 и 8 на месте) || 2
 |-
 | 3 || 0 || <code>1 2 4 5 8</code> || стоп (флаг)
 |}
-Разбор прохода 1 (диапазон <math>j = 0..3</math>): <math>(5,1)</math> → обмен; <math>(5,4)</math> → обмен; <math>(5,2)</math> → обмен; <math>(5,8)</math> — без обмена → <code>1 4 2 5 8</code>. Всего сравнений: <math>4+3+2 = 9</math>. На проходе 3 обменов нет → сортировка завершается по флагу. Трассировка сверена с реализацией из раздела «Служебное».
+Разбор прохода 1 (диапазон <math>j = 0..3</math>): <math>(5,1)</math> → обмен; <math>(5,4)</math> → обмен; <math>(5,2)</math> → обмен; <math>(5,8)</math> — без обмена → <code>1 4 2 5 8</code>. Всего сравнений: <math>4+3+2 = 9</math>. На проходе 3 обменов нет → сортировка завершается по флагу. Числа получены прямым пересчётом по шагам трассировки; базовый псевдокод на этом входе даёт 10 сравнений, а версия с <code>lastSwap</code> — 7 (<math>4+2+1</math>) при тех же 4 обменах.
 == Корректность и оценка сложности ==
@@ Строка 197: / Строка 246: @@
 Сравнений в базовой версии: <math>\sum_{k=0}^{n-2}(n-1-k) = \frac{n(n-1)}{2}</math> — '''независимо''' от входа. Обменов: не более одного на сравнение, до <math>\frac{n(n-1)}{2}</math> (ровно столько на обратном массиве). С флагом лучший случай — <math>n-1</math> сравнений и 0 обменов.
-'''Связь с инверсиями.''' Каждый обмен соседних элементов устраняет ровно одну инверсию и не создаёт новых, поэтому общее число обменов равно числу инверсий исходного массива. Отсюда: обратный массив даёт ровно <math>\frac{n(n-1)}{2}</math> обменов, отсортированный — ноль. Это же объясняет, почему на «почти отсортированных» данных пузырёк с флагом работает за <math>O(n)</math>.
+'''Связь с инверсиями.''' Каждый обмен соседних элементов устраняет ровно одну инверсию и не создаёт новых, поэтому общее число обменов равно числу инверсий исходного массива. Отсюда: обратный массив даёт ровно <math>\frac{n(n-1)}{2}</math> обменов, отсортированный — ноль. Число инверсий объясняет '''число обменов''', но не число проходов: массив <math>[2,3,\dots,n,1]</math> имеет всего <math>n-1</math> инверсию, однако «черепаха» 1 сдвигается влево лишь на одну позицию за проход, поэтому нужны <math>n-1</math> проходов и <math>\Theta(n^2)</math> сравнений. Время <math>O(n)</math> получается только тогда, когда все элементы уже близко к своим местам и хватает одного–двух проходов.
 === Устойчивость ===
@@ Строка 209: / Строка 258: @@
 ! Алгоритм !! Лучший / худший !! Обменов !! Устойчив !! Ниша
 |-
-| '''Пузырёк''' || <math>n</math> (флаг) / <math>n^2</math> || до <math>n^2/2</math> || да || обучение, детект сортировки
+| '''Пузырёк''' || <math>\Theta(n)</math> с флагом / <math>\Theta(n^2)</math> || до <math>\frac{n(n-1)}{2}</math> || да || обучение, детект сортировки
 |-
-| [[Сортировка вставками|Вставками]] || <math>n</math> / <math>n^2</math> || <math>O(n+\text{inv})</math> || да || почти всегда лучше пузырька
+| [[Сортировка вставками|Вставками]] || <math>\Theta(n)</math> / <math>\Theta(n^2)</math> || <math>O(n+\mathit{inv})</math> || да || почти всегда лучше пузырька
 |-
-| [[Сортировка выбором|Выбором]] || <math>n^2</math> / <math>n^2</math> || <math>\le n-1</math> || нет || дорогая запись
+| [[Сортировка выбором|Выбором]] || <math>\Theta(n^2)</math> / <math>\Theta(n^2)</math> || <math>\le n-1</math> || нет || дорогая запись
 |-
-| [[Сортировка Шелла|Шелл]] || <math>n</math> / <math>\approx n^{1.3}</math> || — || нет || средние массивы
+| [[Сортировка Шелла|Шелл]] || <math>\Theta(n\log n)</math> / <math>\Theta(n^2)</math> (зависит от шагов) || — || нет || средние массивы
 |-
-| [[Пирамидальная сортировка|Пирамидальная]] || <math>n\log n</math> / <math>n\log n</math> || <math>O(n\log n)</math> || нет || гарантия, <math>O(1)</math> памяти
+| [[Пирамидальная сортировка|Пирамидальная]] || <math>\Theta(n\log n)</math> / <math>\Theta(n\log n)</math> || <math>O(n\log n)</math> || нет || гарантия, <math>O(1)</math> памяти
 |}
-[[Файл:bs-06-compare.svg|frame|none|700px|Рис. 6. Пузырёк: та же асимптотика, но больше обменов — почти всегда худший выбор.]]
+Примечание: оценка <math>\approx n^{1.3}</math> для сортировки Шелла — эмпирическая средняя, а не худший случай; худший случай зависит от выбранной последовательности шагов.
-'''Вердикт.''' Замените пузырёк на [[Сортировка вставками\|вставки]] (обычно быстрее и меньше перемещений) или на [[Сортировка выбором\|выбор]] (при дорогой записи). Пузырёк держите только для обучения и как источник идеи «флаг адаптивности» и comb sort.
+[[Файл:bs-06-compare.svg|frame|none|700px|Рис. 6. Пузырёк: та же асимптотика, что у вставок и выбора, но больше обменов — на практике почти всегда худший выбор.]]
+'''Вердикт.''' Замените пузырёк на [[Сортировка вставками|вставки]] (обычно быстрее и меньше перемещений) или на [[Сортировка выбором|выбор]] (при дорогой записи). Пузырёк держите только для обучения и как источник идеи «флаг адаптивности» и comb sort.
 == Где применяется ==
-# '''Обучение.''' Самый наглядный пример обменной сортировки с ясным инвариантом «отсортированный хвост» и демонстрацией адаптивности [1][2].
+# '''Обучение.''' Самый наглядный пример сортировки обменом с ясным инвариантом «отсортированный хвост» и демонстрацией адаптивности [1][2].
-# '''Проверка «уже отсортировано».''' С флагом за один проход определяет, отсортирован ли массив (<math>n-1</math> сравнение, 0 обменов) — дешёвая проверка почти готовых данных [3].
+# '''Проверка «уже отсортировано».''' С флагом за один проход определяет, отсортирован ли массив (<math>n-1</math> сравнений, 0 обменов) — дешёвая проверка почти готовых данных [3].
-# '''Comb sort.''' Обобщение пузырька на шаг <math>>1</math> — практичный <math>O(n^{1.3})</math>-эмпирический алгоритм, родственный [[Сортировка шелла\|Шеллу]] [4].
+# '''Comb sort.''' Обобщение пузырька на шаг <math>>1</math> — практичный алгоритм с эмпирической оценкой <math>\approx n^{1.3}</math> сравнений в среднем, родственный [[Сортировка Шелла|Шеллу]] [4][5].
-# '''Встраиваемые и учебные реализации.''' Изредка используется на крошечных массивах из-за предельной простоты; обычно уступает вставкам [3].
+# '''Очень малые массивы.''' На массивах из одного–двух элементов разницы нет; при очень малых <math>n</math> решает простота кода, но и здесь обычно предпочитают вставки [3].
-[[Файл:bs-07-applications.svg|frame|none|700px|Рис. 7. Пузырёк: обучение, детект сортировки, мост к comb sort.]]
+Все четыре ниши — на рис. 7.
+[[Файл:bs-07-applications.svg|frame|none|700px|Рис. 7. Четыре ниши пузырька: обучение, детект сортированности, мост к comb sort, очень малые массивы.]]
 == Историческая справка ==
-Обменные сортировки известны с первых лет вычислительной техники; сам термин '''«bubble sort»''' закрепил '''Дональд Кнут''' в ''The Art of Computer Programming'', т. 3 (§5.2.2), где разобраны его инварианты, число сравнений и обменов и отмечена низкая эффективность [2]. Пузырёк часто приписывают ранним работам по сортировке, но как «рабочий» алгоритм он был вытеснен [[Сортировка вставками\|вставками]] и [[Сортировка выбором\|выбором]] ещё до появления быстрых <math>O(n\log n)</math>-методов.
+Первое описание алгоритма дал '''Эдвард Х. Френд''' (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, 1980) и позже исследовали Лейси и Бокс (1991), назвавшие его comb sort и подобравшие коэффициент уменьшения шага <math>\approx 1.3</math> [4]. Шейкерная сортировка (cocktail shaker sort) — прямой двунаправленный вариант пузырька.
+Обобщение на '''шаг''' — '''comb sort''' — описали '''Влодзимеж Добосевич и Артур Боровы''' (Dobosiewicz, Borowy, 1980) [4]; позже Лейси и Бокс (1991) назвали вариант comb sort и подобрали коэффициент уменьшения шага <math>\approx 1.3</math> [5]. Шейкерная сортировка (cocktail shaker sort) — прямой двунаправленный вариант пузырька.
 == Типичные ошибки и подводные камни ==
-* '''Нет флага — нет адаптивности.''' Без раннего выхода пузырёк делает <math>n^2/2</math> сравнений даже на отсортированном массиве.
+* '''Нет флага — нет адаптивности.''' Без раннего выхода пузырёк делает <math>\frac{n(n-1)}{2}</math> сравнений даже на отсортированном массиве.
 * '''Неверная граница прохода.''' <code>j &lt; n-1-pass</code> (а не <code>n-1</code>), иначе лишние сравнения или выход за массив.
 * '''Неустойчивость при <code>&gt;=</code>.''' Замена сравнения на <code>a[j] &gt;= a[j+1]</code> ломает устойчивость.
-* '''Много обменов.''' До <math>n^2/2</math> обменов против <math>O(n)</math> у выбора — главный минус на практике.
+* '''Много обменов.''' До <math>\frac{n(n-1)}{2}</math> обменов против <math>\le n-1</math> у выбора — главный минус на практике.
-* '''<code>lastSwap</code> как индекс vs позиция.''' Классическая ошибка: сохранять <code>j+1</code> и не сужать границу (см. сноску к optimized-версии).
+* '''<code>lastSwap</code> как индекс vs количество.''' <code>end</code> — индекс, до которого идёт следующий проход: <code>end ← lastSwap</code> даёт экономию, <code>end ← lastSwap + 1</code> — одно лишнее сравнение, а путаница «индекс/количество» при обратном цикле даёт выход за массив.
 * '''Применение на больших массивах.''' <math>O(n^2)</math> неприемлемо; используйте <math>O(n\log n)</math>-алгоритмы.
 * '''Путаница с comb sort.''' Comb sort — не «пузырёк», а его обобщение с шагом; при шаге 1 совпадает с ним.
@@ Строка 272: / Строка 325: @@
 # '''Сравнение.''' Для <math>n = 1000</math> сравните сравнения и обмены пузырька, вставок и выбора. ''Подсказка:'' вставки адаптивны, выбор экономит обмены.
+'''Ответы.'''
+# <math>\frac{n(n-1)}{2}</math> сравнений; на <code>[5,1,4,2,8]</code> — 10 сравнений и 4 обмена.
+# Для <math>n = 10\,000</math>: 9999 сравнений, 0 обменов, один проход.
+# <code>[5,1,4,2,8]</code>: 7 сравнений (<math>4+2+1</math>) против 9 у версии с флагом и фиксированным сужением.
+# <code>[2,3,…,n,1]</code>: пузырёк с флагом — <math>n-1</math> проходов и <math>\approx \frac{n^2}{2}</math> сравнений; шейкер сортирует такой вход за один круг (<math>\approx 2n</math> сравнений: <math>n-1</math> вперёд и <math>n-2</math> назад), но без флага продолжает круги и делает <math>\approx \frac{n^2}{2}</math> сравнений (45 при <math>n = 10</math>); с флагом он останавливается на первом проходе без обменов — это уже второй круг, а не первый.
+# Обмен возможен только при сравнении, поэтому обменов не больше; на обратном массиве каждая пара — инверсия, ровно <math>\frac{n(n-1)}{2}</math>.
+# Пары <code>(1,a)</code>, <code>(1,b)</code>: при <code>&gt;=</code> обмен меняет метки местами, при <code>&gt;</code> порядок сохраняется.
+# При шаге 1 comb sort совпадает с пузырьком с флагом; «черепаха» в конце устраняется первым проходом с большим шагом.
+# Для <math>n = 1000</math>: пузырёк и выбор — ровно 499 500 сравнений; у выбора <math>\le 999</math> обменов; вставки в среднем — <math>\approx \frac{n^2}{4}</math> сравнений и перемещений, на отсортированном — <math>n-1</math>.
 == Связанные темы ==
-* [[Сортировки]] — обзор и нижняя граница <math>\Omega(n\log n)</math>.
+* [[Сортировки]] (план) — обзор и нижняя граница <math>\Omega(n\log n)</math>.
-* [[Сортировка вставками]] — почти всегда лучшая замена пузырька.
+* [[Сортировка вставками]] (план) — почти всегда лучшая замена пузырька.
-* [[Сортировка выбором]] — минимум записей.
+* [[Сортировка выбором]] (план) — минимум записей.
-* [[Сортировка Шелла]] — родственник через comb sort.
+* [[Сортировка Шелла]] (план) — родственник через comb sort.
-* [[Асимптотическая сложность]] — лучший/средний/худший случаи.
+* [[Асимптотическая сложность]] (план) — лучший/средний/худший случаи.
 == Источники ==
-# Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. ''Introduction to Algorithms'' (CLRS). 3rd ed. — MIT Press, 2009. — Задача 2-2 (bubble 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 (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. 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).
+# Dobosiewicz W., Borowy A. An efficient variation of bubble sort // Information Processing Letters. — 1980. — Vol. 11, No. 1. — P. 5–6.
-# Wikipedia: Bubble sort. URL: https://en.wikipedia.org/wiki/Bubble_sort .
+# 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.
 [[Category:Сортировки]]