Принцип работы алгоритма сортировки пузырьком метафорически соответствует его названию: более легкие (или более тяжелые, в зависимости от направления) элементы «всплывают» наверх, подобно пузырькам в воде. Алгоритм последовательно проходит по массиву, сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке. Этот процесс повторяется до тех пор, пока массив не будет полностью отсортирован, то есть пока за весь проход не будет совершено ни одного обмена.
Пошаговая инструкция работы алгоритма на примере массива [5, 1, 4, 2, 8]:
Шаг 1 (Первый проход по массиву):
* Сравниваем 5 и 1. 5 > 1, поэтому меняем их местами. Массив становится [1, 5, 4, 2, 8].
* Сравниваем 5 и 4. 5 > 4, меняем. Массив: [1, 4, 5, 2, 8].
* Сравниваем 5 и 2. 5 > 2, меняем. Массив: [1, 4, 2, 5, 8].
* Сравниваем 5 и 8. 5 < 8, порядок верный, оставляем как есть. Массив: [1, 4, 2, 5, 8].
После первого прохода самый большой элемент (8) «всплыл» на свою конечную позицию в конце массива.
Шаг 2 (Второй проход):
* Теперь проходим по неотсортированной части массива (первые 4 элемента). Сравниваем 1 и 4. Порядок верный.
* Сравниваем 4 и 2. 4 > 2, меняем. Массив: [1, 2, 4, 5, 8].
* Сравниваем 4 и 5. Порядок верный.
Второй по величине элемент (5) встал на свою позицию.
Шаг 3 (Третий проход):
* Проходим по первым трем элементам. Сравниваем 1 и 2. Порядок верный.
* Сравниваем 2 и 4. Порядок верный.
Ни одного обмена не произошло, но алгоритм в базовой версии должен завершить проход.
Шаг 4 (Четвертый проход):
* Проходим по первым двум элементам. Сравниваем 1 и 2. Порядок верный.
Снова обменов нет. После этого прохода (или после оптимизированной проверки) алгоритм завершает работу. Массив отсортирован: [1, 2, 4, 5, 8].
Анализ сложности:
* Временная сложность в худшем и среднем случае составляет O(n²), где n — количество элементов. Это связано с вложенными циклами: для каждого элемента мы в худшем случае проходим почти по всему массиву.
* В лучшем случае, когда массив уже отсортирован, наивная реализация все равно выполнит O(n²) операций. Однако с оптимизацией (флаг swapped) лучшая сложность становится O(n).
* Пространственная сложность — O(1), так как алгоритм сортирует на месте, используя лишь постоянный объем дополнительной памяти для временной переменной обмена.
Оптимизации базового алгоритма:
- Флаг обменов (swapped). Если во внутреннем цикле не было произведено ни одного обмена, массив уже отсортирован, и можно досрочно выйти из внешнего цикла.
- Учет отсортированного хвоста. После каждого просканирования массива самый большой элемент встает в конец. Поэтому внутренний цикл можно ограничивать не до конца массива, а до индекса, который еще не отсортирован.
Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
Java:
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) break;
}
}
JavaScript:
function bubbleSort(arr) {
let n = arr.length;
let swapped;
for (let i = 0; i < n - 1; i++) {
swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
Когда использовать сортировку пузырьком? Практически никогда в production-коде для больших массивов. Ее время выполнения быстро становится неприемлемым с ростом объема данных. Однако она находит применение в образовательных целях, для сортировки маленьких массивов (где накладные расходы на вызов более сложного алгоритма могут превысить выгоду), или в специфических контекстах, где важна предельная простота реализации, а данные почти отсортированы (с оптимизацией swapped).
Изучение сортировки пузырьком — это важный ритуал посвящения в мир алгоритмов. Она наглядно демонстрирует разницу между квадратичной и линейно-логарифмической сложностью, важность оптимизаций и то, как простота концепции может обернуться серьезными практическими ограничениями. Это фундамент, на котором строится понимание более продвинутых алгоритмов, таких как быстрая сортировка или сортировка слиянием.
Комментарии (13)