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

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

Столбики разной высоты в процессе сортировки: два соседних выделены для обмена, а самые высокие уже стоят на своих местах в конце
Столбики разной высоты в процессе сортировки: два соседних выделены для обмена, а самые высокие уже стоят на своих местах в конце

Идея

Пройдите по списку слева направо и смотрите на каждую пару соседей. Если левое значение больше правого, поменяйте их местами. Когда вы дойдёте до конца, наибольшее значение окажется на последнем месте — так пузырёк поднимается на поверхность. Такой обход называется проходом. Повторяйте проходы, пока список не будет отсортирован.

Пример

Возьмём 5, 1, 4, 2, 8. Первый проход сравнивает 5 и 1 и меняет их местами, затем 5 и 4 (обмен), 5 и 2 (обмен) и 5 и 8 (без обмена): 1, 4, 2, 5, 8. Теперь 8 стоит на своём окончательном месте. Второй проход сравнивает 1 и 4 (без обмена), 4 и 2 (обмен) и 4 и 5 (без обмена): 1, 2, 4, 5, 8. Третий проход не делает ни одного обмена, значит, список отсортирован: 9 сравнений и 4 обмена.

Почему каждый проход ставит на место ещё одно значение

Во время прохода наибольшее из уже встреченных значений всегда движется дальше: как только проход до него доходит, каждое сравнение сдвигает его на одно место вправо. Поэтому первый проход ставит наибольшее значение в конец, второй — второе по величине прямо перед ним, и так далее. После k-го прохода последние k мест окончательны, и следующий проход может закончиться на одно место раньше. Вот почему проходы становятся короче.

Обменов столько же, сколько инверсий

Инверсия — это пара значений в неправильном порядке: большее значение стоит где-то перед меньшим. Обмен двух соседей, стоящих не по порядку, убирает ровно одну инверсию и не создаёт новых. Поэтому сортировка пузырьком делает ровно столько обменов, сколько инверсий в начальном списке, в каком бы порядке ни шли сравнения. В отсортированном списке инверсий нет; в обратном списке из n значений их n(n − 1)/2 — максимально возможное число.

Ранняя остановка и стоимость

Если за весь проход не было обменов, все соседи стоят по порядку и список отсортирован. Такая проверка позволяет закончить отсортированный список за один проход из n − 1 сравнений. В худшем случае всё равно нужны n − 1 проходов и n(n − 1)/2 сравнений, а в среднем делается n(n − 1)/4 обменов. Оба числа растут как n², поэтому вдвое более длинный список сортируется примерно в четыре раза дольше.

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

Попробуйте сами

Откройте приложение и нажмите «Пуск» или «Шаг», чтобы идти по одному сравнению. Два сравниваемых значения подсвечиваются, обмен показан своим цветом, а значения, которые уже на месте, становятся зелёными. Возьмите обратный список, чтобы увидеть худший случай, почти отсортированный — чтобы увидеть, как ранняя остановка завершает сортировку через несколько проходов, или введите числа из примера выше.

Часто задаваемые вопросы

Какова временная сложность сортировки пузырьком?

O(n²) в худшем и среднем случае: до n(n − 1)/2 сравнений для n значений. С ранней остановкой уже отсортированный список требует O(n), то есть одного прохода. Дополнительной памяти нужно всего O(1).

Устойчива ли сортировка пузырьком?

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

Чем сортировка пузырьком отличается от сортировки вставками?

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

Когда сортировка пузырьком — хороший выбор?

В основном для обучения и для очень коротких списков, где простота важнее скорости. Для всего, что больше, встроенная сортировка вашего языка программирования намного быстрее.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать сортировку пузырьком