Сортировка пузырьком — один из самых простых для понимания алгоритмов упорядочивания данных. Несмотря на то что в реальных проектах он используеться редко из-за невысокой эффективности, знание этого метода является фундаментальным для любого программиста. В данной статье мы подробно разберём принцип работы алгоритма, пошагово рассмотрим его логику, реализуем на языке Python и проанализируем сложность.

Описание алгоритма

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

Алгоритм получил своё название благодаря тому, что наибольшие (или наименьшие) элементы постепенно «всплывают» к краю списка, подобно пузырькам воздуха в воде.

Пошаговый пример работы

Рассмотрим сортировку списка [5, 3, 8, 4, 2] по возрастанию:

1. Проход 1: 5 и 3 меняются местами → [3, 5, 8, 4, 2]; 5 и 8 остаются; 8 и 4 меняются → [3, 5, 4, 8, 2]; 8 и 2 меняются → [3, 5, 4, 2, 8]. Число 8 встало на место.
2. Проход 2: 3 и 5 остаются; 5 и 4 меняются → [3, 4, 5, 2, 8]; 5 и 2 меняются → [3, 4, 2, 5, 8]. Число 5 встало на место.
3. Проход 3: 3 и 4 остаются; 4 и 2 меняются → [3, 2, 4, 5, 8].
4. Проход 4: 3 и 2 меняются → [2, 3, 4, 5, 8].

После четырёх проходов список полностью отсортирован.

Базовая реализация в Python

Ниже представлена классическая реализация алгоритма. Внешний цикл отвечает за количество проходов, а внутренний, за сравнение соседних пар.

def bubble_sort(arr):
 n = len(arr)
 for i in range(n):
 for j in range(0, n ― i ⎯ 1):
 if arr[j] > arr[j + 1]:

 # Обмен элементов
 arr[j], arr[j + 1] = arr[j + 1], arr[j]
 return arr

numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print("Отсортированный список:", sorted_numbers)

Оптимизированная версия

Основной недостаток базового алгоритма — он выполняет все проходы даже если список уже отсортирован. Для оптимизации можно ввести флаг, который будет отслеживать, произошли ли обмены во время текущего прохода. Если обменов не было, значит массив уже упорядочен, и можно завершить работу раньше.

def bubble_sort_optimized(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 swappedswapped:
 break
 return arr

Анализ сложности

• Время в лучшем случае: O(n) — для оптимизированной версии, когда массив уже отсортирован.
• Время в среднем и худшем случае: O(n²) — когда элементы расположены в случайном или обратном порядке.

collapsed for brevity; will include in final output.

• Пространственная сложность: O(1), алгоритм сортирует элементы прямо в исходном списке, не требуя дополнительной памяти.

Преимущества и недостатки

Преимущества:

• Простота реализации и понимания.
• Стабильность — не меняет порядок равных элементов.
• Не требует дополнительной памяти (сортировка «на мест»).

Недостатки:

• Низкая производительность на больших массивах данных.
• Значительное количество операций сравнения и обмена.

Когда использовать Bubble Sort

Несмотря на простоту, сортировка пузырьком практически не используется в production-коде для обработки больших объёмов данных. Её можно применять для:

• Учебных целей и изучения основ алгоритмизации.
• Сортировки небольших списков, где скорость не критична.
• Ситуаций, когда важна минимизация расхода памяти, а скорость работы является второстепенным фактором.

Сортировка пузырьком, это базовый алгоритм, который помогает понять принципы работы циклов, условий и обмена значений в Python. Хотя для реальных задач предпочтительнее использовать встроенные методы вроде sort или sorted, ручная реализация Bubble Sort развивает алгоритмическое мышление и служит хорошей отправной точкой для изучения более сложных методов сортировки, таких как быстрая сортировка или сортировка слиянием.