Название этого метода идёт от красивой аналогии с пузырьками воздуха в воде: пузырёк всегда стремится всплыть наверх.
Так же и в массиве: при проходе мы сравниваем соседние элементы и «выталкиваем» наибольший из них в конец массива.
За один такой проход мы гарантированно получим правильный максимальный элемент в самом конце. Далее мы повторяем процесс, но уже на сокращённом массиве, исключив последний элемент.
Идея алгоритма
- Начинаем с самого начала массива.
- Сравниваем элементы попарно: arr[i] и arr[i+1].
- Если они стоят в неправильном порядке (левый больше правого), меняем их местами.
- После первого прохода самый большой элемент «всплывает» в конец массива.
- Повторяем то же самое, каждый раз уменьшая рассматриваемую часть массива на один элемент.
Так как на каждом шаге мы проверяем пары, алгоритм стабилен: если встречаются равные элементы, их порядок в итоговой последовательности не изменится.
Сложность алгоритма
На первый взгляд пузырьковая сортировка кажется простой. Но если мы внимательно посмотрим, то за каждый проход по массиву мы делаем примерно n сравнений, а самих проходов тоже порядка n.
Поэтому сложность алгоритма — O(n²).
Однако есть оптимизация: если в каком-то проходе мы не сделали ни одного обмена, значит, массив уже отсортирован, и можно завершить работу.
Рекурсивный вариант
def bubble_sort_recursive(arr, length=None):
"""Рекурсивная пузырьковая сортировка"""
if length is None:
length = len(arr)
if length > 1:
for i in range(length - 1):
# Меняем местами элементы, если они стоят неправильно
if arr[i] > arr[i + 1]:
arr[i], arr[i + 1] = arr[i + 1], arr[i]
# Рекурсивный вызов на сокращённом массиве
bubble_sort_recursive(arr, length - 1)
# Пример
nums = [5, 1, 4, 2, 8]
bubble_sort_recursive(nums)
print(nums) # [1, 2, 4, 5, 8]Итеративный вариант (с оптимизацией)
def bubble_sort_iter(arr):
"""Итеративная пузырьковая сортировка с проверкой на упорядоченность"""
n = len(arr)
for i in range(n):
sorted_flag = True
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
sorted_flag = False
# Если обменов не было — массив уже отсортирован
if sorted_flag:
break
# Пример
nums = [5, 1, 4, 2, 8]
bubble_sort_iter(nums)
print(nums) # [1, 2, 4, 5, 8]Вариант для NumPy
import numpy as np
def bubble_sort_numpy(arr):
"""Итеративная пузырьковая сортировка для numpy.array"""
arr = arr.copy() # Чтобы не портить исходный массив
n = len(arr)
for i in range(n):
sorted_flag = True
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
sorted_flag = False
if sorted_flag:
break
return arr
# Пример
arr = np.array([64, 34, 25, 12, 22, 11, 90])
print(bubble_sort_numpy(arr)) # [11 12 22 25 34 64 90]Пузырьковая сортировка — один из самых простых для понимания алгоритмов, но на практике почти не используется из-за своей квадратичной сложности.
Тем не менее, её важно разобрать:
- она помогает понять идею пошагового упорядочивания массива,
- она показывает пример стабильной сортировки,
- на её основе удобно вводить тему оптимизаций и проверки на упорядоченность.