Сортировка пузырьками — это самая наверно распространенная сортировка, одна из самых простых, про которую знают практически все, но при этом ее стараются не применять. Все дело в скорости выполнения -сложности этого алгоритма. Смысл сортировки пузырьками заключается в том что перебирать список и отправлять за один проход самое большое значение в конец списка. Заключается в прохождении двух циклов. Циклы могут быть как 2 цикла for так и один for второй whie. Внешний цикл отвечает за перебор каждого из элементов последовательности. Внутренний цикл отвечает за движение самого большого значения в конец списка.
Внешний цикл проходит по всем элементам списка.
Внутренний цикл сравнивает пары соседних элементов и переставляет их, если нужно.
Сложность алгоритма
В худшем среднем и лучшем случае: O(n**2) квадратичная сложность про классическую пузырьковую сортировку нужен обход двух циклов
В лучшем случае при модернизации O(n) - если список уже отсортирован, это про модернизацию сортировки которая приведена ниже.
Таким образом, время выполнения линейно зависит от размера данных: чем больше список, тем дольше сортировка.
Пример реализации на Python
def bubble_sorting(value):
n = len(value)-1
for i in range(n):
for c in range(0, n):
if value[c] > value[c+1]:
value[c], value[c+1] = value[c+1], value[c]
return value
#можно ускорить этот алгоритм. Мы знаем что максимальное значение уже будет
#в конце после первого выполнения внутреннего цикла так зачем нам каждый
#раз проверять какое у нас последне предпоследнее итак далее значение
def bubble_sorting2(value):
n = len(value)-1
for i in range(n):
for c in range(0, n - i):
if value[c] > value[c+1]:
value[c], value[c+1] = value[c+1], value[c]
return value
#а что если список уже был частично осортирован зачем проверять все значения еще раз
def bubble_sorting3(value):
n = len(value)-1
for i in range(n):
flag = True # думаем что отсортировано
for c in range(0, n - i):
if value[c] > value[c+1]:
value[c], value[c+1] = value[c+1], value[c]
flag = False # ошиблись не отсортирован
if flag:
break
return value
# как только какой то цикл не произведен ни одной замены сортировка прекратится
#посмотрим как повлияли наши улучшения на скорость выполнения цикла
#возьмем цикл из 10 чисел, отсортированный на половину
Проверка улучшений
#посмотрим как повлияли наши улучшения на скорость выполнения цикла
#возьмем цикл из 9 чисел, отсортированный на половину
list_ = [1,2,3,4,5,1,3,5,4]
#1
def bubble_sorting(value):
n = len(value)-1
totall = 0
for i in range(n):
for c in range(0, n):
totall += 1
if value[c] > value[c+1]:
value[c], value[c+1] = value[c+1], value[c]
return value, totall
#2
def bubble_sorting2(value):
n = len(value)-1
totall = 0
for i in range(n):
for c in range(0, n - i):
totall += 1
if value[c] > value[c+1]:
value[c], value[c+1] = value[c+1], value[c]
return value, totall
#3
def bubble_sorting3(value):
n = len(value)-1
totall = 0
for i in range(n):
flag = True # думаем что отсортировано
for c in range(0, n - i):
totall += 1
if value[c] > value[c+1]:
value[c], value[c+1] = value[c+1], value[c]
flag = False # ошиблись не отсортирован
if flag:
break
return value, totall
list1, totall1 = bubble_sorting(list_)
list2, totall2 = bubble_sorting2(list_)
list3, totall3 = bubble_sorting3(list_)
print(f'Простая сортировка пузырьком нужно {totall1} итераций,\n'
f'усовершенствованная 2 нужно {totall2} итераций,\n'
f'усовершенствованная 3 нужно {totall3} итераций ')
--> Простая сортировка пузырьком нужно 64 итераций,
--> усовершенствованная 2 нужно 36 итераций,
--> усовершенствованная 3 нужно 8 итераций
Обычная версия делает лишние проверки.
Сокращение диапазона ускоряет сортировку почти в 2 раза.
Ранний выход даёт максимальное ускорение, если данные частично упорядочены.
Сортировка пузырьком — хороший учебный пример, но на практике лучше использовать более эффективные алгоритмы, такие как быстрая сортировка (Quick Sort) или сортировка слиянием (Merge Sort).
Если всё же нужно использовать пузырьковую сортировку, лучше применять оптимизированные версии, чтобы уменьшить время работы.