Как работает пузырьковая сортировка
Алгоритм многократно проходит по массиву слева направо, сравнивая соседние элементы. Если левый больше правого — они меняются местами. После каждого прохода максимальный элемент из ещё не отсортированной части «всплывает» в конец, как пузырёк воздуха в воде. Проходы повторяются до тех пор, пока за целый проход не произойдёт ни одного обмена — это означает, что массив уже отсортирован.
Пузырьковая сортировка — алгоритм сравнения (comparison sort), устойчивый (stable) и адаптивный (adaptive). Устойчивость означает, что равные элементы сохраняют относительный порядок. Адаптивность — на почти отсортированных данных алгоритм работает за O(n).
Базовая реализация на C
C:
#include <stdio.h>
void bubble_sort(int arr[], int n)
{
int swapped;
do {
swapped = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = 1;
}
}
} while (swapped);
}
int main(void)
{
int arr[] = {5, 1, 4, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, n);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}Вывод программы:
Код:
1 2 4 5 8Флаг
swapped позволяет завершить работу досрочно: если за проход не было ни одного обмена, массив уже отсортирован и дальнейшие итерации бессмысленны.Пошаговая трассировка на примере
Возьмём массив
{5, 1, 4, 2, 8} и проследим каждый проход.Проход 1:
| Сравнение | Массив после обмена |
|---|---|
| 5 > 1 → обмен | {1, 5, 4, 2, 8} |
| 5 > 4 → обмен | {1, 4, 5, 2, 8} |
| 5 > 2 → обмен | {1, 4, 2, 5, 8} |
| 5 < 8 → без обмена | {1, 4, 2, 5, 8} |
Максимальный элемент (8) уже на своём месте.
Проход 2:
| Сравнение | Массив после обмена |
|---|---|
| 1 < 4 → без обмена | {1, 4, 2, 5, 8} |
| 4 > 2 → обмен | {1, 2, 4, 5, 8} |
| 4 < 5 → без обмена | {1, 2, 4, 5, 8} |
| 5 < 8 → без обмена | {1, 2, 4, 5, 8} |
Проход 3:
Ни одного обмена не произошло — алгоритм останавливается.
Обратите внимание: даже когда массив уже отсортирован после второго прохода, алгоритму нужен ещё один проход без обменов, чтобы «понять», что работа завершена.
Оптимизация: сужение границы внутреннего цикла
После каждого прохода последний элемент неотсортированной части гарантированно стоит на месте. Значит, внутренний цикл можно укорачивать:
C:
void bubble_sort_shrinking(int arr[], int n)
{
int swapped;
do {
swapped = 0;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = 1;
}
}
n--;
} while (swapped);
}Здесь
n уменьшается на единицу после каждого прохода. Количество сравнений сокращается с n·(n−1) до n·(n−1)/2 — вдвое меньше в худшем случае.Оптимизация: запоминание позиции последнего обмена
Если за проход последний обмен произошёл на позиции
k, то все элементы правее k уже отсортированы. Можно сразу перенести границу туда:
C:
void bubble_sort_last_swap(int arr[], int n)
{
while (n > 1) {
int newn = 0;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
int tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
newn = i;
}
}
n = newn;
}
}Эта версия даёт до 50 % экономии на количестве сравнений в худшем случае по сравнению с базовой реализацией, при этом количество обменов остаётся тем же.
Сложность алгоритма
| Случай | Время | Память |
|---|---|---|
| Худший (обратный порядок) | O(n²) | O(1) |
| Средний | O(n²) | O(1) |
| Лучший (уже отсортирован) | O(n) | O(1) |
Лучший случай достигается благодаря флагу
swapped: один проход без обменов — и алгоритм завершается. Это свойство делает пузырьковую сортировку адаптивной.Проблема «черепах» и «кроликов»
Элементы, которые должны двигаться к концу массива, перемещаются быстро — они участвуют в последовательных обменах и за один проход могут пройти весь путь. Такие элементы называют «кроликами». Максимальный элемент всегда достигает своей позиции за первый проход.
Элементы, которые должны двигаться к началу, перемещаются не быстрее чем на одну позицию за проход. Минимальный элемент в конце массива потребует n−1 проходов, чтобы оказаться в начале. Такие элементы называют «черепахами».
Именно черепахи определяют худший случай. Двусторонняя модификация (cocktail sort) решает эту проблему, чередуя направление проходов, но сохраняет сложность O(n²).
Устойчивость сортировки
Пузырьковая сортировка устойчива: если два элемента равны, их относительный порядок не меняется. Обмен происходит только при строгом неравенстве
arr[i] > arr[i + 1]. Если заменить > на >=, устойчивость теряется — это распространённая ошибка при модификации алгоритма.Типичные ошибки начинающих
Выход за границы массива. Внутренний цикл должен идти до
n - 2 (или i < n - 1), потому что внутри цикла происходит обращение к arr[i + 1]. Если написать i < n, произойдёт чтение за пределами массива — неопределённое поведение.Забытый флаг раннего выхода. Без
swapped алгоритм всегда выполняет n−1 проходов, даже если массив отсортирован за один. Это не ошибка корректности, но потеря адаптивности.Неправильный размер при передаче в функцию. В C массив, переданный в функцию, вырождается в указатель.
sizeof(arr) внутри функции вернёт размер указателя, а не массива. Размер всегда нужно передавать отдельным параметром.Переполнение при обмене через арифметику. Иногда встречается «обмен без временной переменной» через сложение или XOR. При сложении двух больших
int возможно переполнение. Используйте классический обмен через временную переменную — он безопасен и читаем.Сравнение с сортировкой вставками
Пузырьковая сортировка и сортировка вставками (insertion sort) имеют одинаковую асимптотическую сложность O(n²), но на практике insertion sort работает заметно быстрее. Причины:
- Пузырьковая сортировка выполняет примерно вдвое больше записей в память.
- Она порождает больше промахов кэша и ошибок предсказания ветвлений.
- Эксперименты показывают, что пузырьковая сортировка работает примерно в пять раз медленнее сортировки вставками на случайных данных.
Именно поэтому в современных учебниках и стандартных библиотеках пузырьковую сортировку не используют. Её ценность — педагогическая: это самый простой способ понять механику сортировки сравнением.
Когда пузырьковая сортировка уместна
Несмотря на низкую производительность, у алгоритма есть ниша:
- Обучение. Минимальный код, понятная логика, легко трассировать вручную.
- Почти отсортированные данные. Если в массиве лишь несколько инверсий, адаптивность даёт O(n) — быстрее, чем quicksort с его гарантированными O(n log n).
- Компьютерная графика. В алгоритмах заполнения полигонов порядок граничных линий меняется на одну-две перестановки при переходе к следующей строке развёртки. Пузырьковая сортировка исправляет такие ошибки за линейное время.
Проверка результата
Простая функция верификации, которую полезно писать при отладке:
C:
#include <stdio.h>
int is_sorted(const int arr[], int n)
{
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1])
return 0;
}
return 1;
}Вызывайте её после сортировки в отладочных сборках. Для больших массивов можно сравнивать результат с эталонной сортировкой через
qsort из <stdlib.h>.Итоговый чек-лист для реализации
- Внутренний цикл:
iот 0 доn - 2включительно (илиi < n - 1).
- Обмен только при строгом
>для сохранения устойчивости.
- Флаг
swappedдля раннего выхода на отсортированных данных.
- Размер массива передаётся отдельным аргументом.
- Обмен через временную переменную, без арифметических трюков.
- После сортировки — проверка
is_sortedв отладочном режиме.
- Для массивов больше нескольких тысяч элементов — переходите на
qsortили собственную реализацию O(n log n).