СВ: Новая страница: «== TL;DR == '''Сортировка пузырьком''' (bubble sort) многократно проходит по массиву, сравнивая '''сос...»

2026-09-30T19:13:45Z

Новая страница: «== TL;DR == '''Сортировка пузырьком''' (bubble sort) многократно проходит по массиву, сравнивая '''сос...»

Новая страница

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

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

== Определения ==

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

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

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

'''На месте (in-place)''' — <math>O(1)</math> дополнительной памяти.

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

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

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

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

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

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

[[Файл:bs-01-idea.svg|frame|none|700px|Рис. 1. Сравниваем соседние пары; больший «всплывает» вправо, максимум доходит до конца.]]

[[Файл:bs-02-adaptive.svg|frame|none|700px|Рис. 2. Флаг раннего выхода превращает пузырёк в адаптивный: отсортированный вход — <math>n-1</math> сравнений.]]

== Устройство ==

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

[[Файл:bs-03-pass.svg|frame|none|700px|Рис. 3. Один проход: диапазон <math>j = 0 \dots n-2-\text{pass}</math>; максимум уходит вправо.]]

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

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

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

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

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

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

# Для <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] > a[j+1]</code>, обменять.

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

<syntaxhighlight lang="text">
Алгоритм 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])
</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 — без обменов (стоп при оптимизации).

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

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

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

<syntaxhighlight lang="text">
Алгоритм 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 → выход
</syntaxhighlight>

'''Разбор.''' Отсортированный вход: один проход, <code>lastSwap = 0</code> → <code>end = 0</code> → стоп, <math>n-1</math> сравнений.

'''Сложность.''' Лучший <math>\Theta(n)</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. Проходы, сужение границы и досрочный выход по отсутствию обменов.]]

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

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

<syntaxhighlight lang="text">
Алгоритм 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
</syntaxhighlight>

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

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

[[Файл:bs-05-cocktail.svg|frame|none|700px|Рис. 5. Проходы в обе стороны; минимум и максимум ставятся на место за круг.]]

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

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

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

{| class="wikitable"
|-
! Вариант !! Лучший !! Средний !! Худший !! Обменов !! Память
|-
| Базовая || <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)</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>n^2/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>
|}

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

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

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

{| class="wikitable"
|-
! Проход !! Обменов !! Массив после !! Граница
|-
| старт || — || <code>5 1 4 2 8</code> || 4
|-
| 1 || 3 || <code>1 4 2 5 8</code> || 3
|-
| 2 || 1 || <code>1 2 4 5 8</code> || 1
|-
| 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 обменов нет → сортировка завершается по флагу. Трассировка сверена с реализацией из раздела «Служебное».

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

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

'''Инвариант.''' Перед проходом <math>k</math> последние <math>k</math> элементов массива отсортированы и не меньше всех остальных.

'''База.''' <math>k = 0</math>: хвост пуст — верно.

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

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

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

Сравнений в базовой версии: <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>.

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

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

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

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

[[Файл:bs-06-compare.svg|frame|none|700px|Рис. 6. Пузырёк: та же асимптотика, но больше обменов — почти всегда худший выбор.]]

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

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

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

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

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

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

[[Файл: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>-методов.

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

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

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

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

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

# '''Флаг.''' Добавьте ранний выход и покажите, что на отсортированном массиве <math>n-1</math> сравнений. ''Подсказка:'' флаг обмена.

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

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

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

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

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

# '''Сравнение.''' Для <math>n = 1000</math> сравните сравнения и обмены пузырька, вставок и выбора. ''Подсказка:'' вставки адаптивны, выбор экономит обмены.

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

* [[Сортировки]] — обзор и нижняя граница <math>\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. — Задача 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; анализ).
# 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).
# Wikipedia: Bubble sort. URL: https://en.wikipedia.org/wiki/Bubble_sort .

← Предыдущая		Версия 19:14, 30 сентября 2026
Строка 288:		Строка 288:
	# 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. 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).
	# Wikipedia: Bubble sort. URL: https://en.wikipedia.org/wiki/Bubble_sort .		# Wikipedia: Bubble sort. URL: https://en.wikipedia.org/wiki/Bubble_sort .

			[[Category:Сортировки]]

Сортировка пузырьком - История изменений

СВ: /* Связанные темы */

СВ в 13:33, 26 октября 2026

СВ: /* Источники */

СВ: Новая страница: «== TL;DR == '''Сортировка пузырьком''' (bubble sort) многократно проходит по массиву, сравнивая '''сос...»

← Предыдущая		Версия 22:14, 27 октября 2026
Строка 339:		Строка 339:
	== Связанные темы ==		== Связанные темы ==

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

	== Источники ==		== Источники ==