Post #1532
498
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
# Пример 1: Обычная сортировка
data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(data1.copy()))
# Результат: [11, 12, 22, 25, 34, 64, 90]
# Пример 2: Уже отсортированный список
data2 = [1, 2, 3, 4, 5]
print(bubble_sort(data2.copy()))
# Результат: [1, 2, 3, 4, 5]
# Пример 3: Обратный порядок
data3 = [5, 4, 3, 2, 1]
print(bubble_sort(data3.copy()))
# Результат: [1, 2, 3, 4, 5]
Чтобы лучше проследить за ходом алгоритма, можно использовать визуализированную версию:
def bubble_sort_visualized(arr):
n = len(arr)
print(f"Начальный список: {arr}")
print()
for i in range(n):
print(f"=== Проход {i + 1} ===")
swapped = False
for j in range(0, n - i - 1):
print(f"Сравниваем {arr[j]} и {arr[j + 1]}", end=" ")
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
print(f"→ Меняем! Теперь: {arr}")
else:
print(f"→ Оставляем")
if not swapped:
print("Обменов не было, список отсортирован!")
break
print()
print(f"\nИтоговый список: {arr}")
return arr
data = [5, 2, 8, 1, 9]
bubble_sort_visualized(data)
Одним из недостатков пузырьковой сортировки является её низкая эффективность на больших наборах данных. Сложность алгоритма в худшем и среднем случае оценивается как O(n²), где n — количество элементов. Это означает, что с ростом размера списка количество необходимых операций сравнения и обмена растёт квадратично. Например, для тысячи элементов может потребоваться около миллиона сравнений, в то время как более совершенные алгоритмы, такие как быстрая сортировка, справляются с этой задачей за порядка двадцати тысяч операций. Именно поэтому пузырьковая сортировка, при всей своей простоте и наглядности, не применяется в реальных проектах с большими объёмами данных.
Алгоритм можно модифицировать для сортировки по убыванию. Для этого достаточно изменить условие сравнения с
> на <, чтобы более мелкие элементы перемещались вправо:def bubble_sort_descending(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
data1 = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort_descending(data1.copy()))
# Результат: [90, 64, 34, 25, 22, 12, 11]
Также можно создать универсальную функцию, принимающую параметр
reverse для выбора направления сортировки.В заключение, пузырьковая сортировка служит отличным учебным инструментом для понимания базовых принципов алгоритмов сортировки. Она проста для восприятия и реализации, корректно работает на любых данных, но из-за квадратичной сложности неприменима для серьёзных задач. Её изучение даёт необходимую основу для перехода к более эффективным алгоритмам.
#algorithm
- 👍 4
- 🐳 1
