Пузырьковая сортировка
Пузырьковая сортировка — простой алгоритм упорядочивания массива: он многократно сравнивает соседние элементы и меняет их местами, если они расположены не в требуемом порядке.
Для массива из \(n\) элементов обычно выполняют до \(n-1\) проходов. После первого прохода самый большой элемент оказывается последним, после второго — второй по величине занимает предпоследнее место и так далее. На каждом проходе последнюю уже упорядоченную часть можно не просматривать.
Формула показывает максимальное число сравнений в обычном варианте алгоритма: \(C\) — число сравнений, \(n\) — количество элементов. В лучшем случае, если массив уже упорядочен и используется проверка отсутствия обменов, достаточно одного прохода.
Пусть массив равен \([4, 2, 3]\). Сравниваем \(4\) и \(2\): порядок нарушен, получаем \([2, 4, 3]\). Затем сравниваем \(4\) и \(3\): снова меняем элементы и получаем \([2, 3, 4]\). На следующем проходе обменов нет, поэтому алгоритм можно завершить.
Пузырьковая сортировка не выбирает сразу минимальный элемент, как сортировка выбором, и не вставляет очередной элемент в готовую часть, как сортировка вставками. В ней выполняются именно обмены соседних элементов.
Что произойдёт с парой соседних элементов \(7\) и \(5\) при сортировке по возрастанию?
Главное
- Алгоритм сравнивает соседние элементы и обменивает их при нарушении порядка.
- За проход крупные элементы перемещаются вправо; максимум сравнений равен \(\frac{n(n-1)}{2}\).
- Для досрочного завершения проверяют, были ли обмены на текущем проходе.