Метод "бульбашки" та змішуванням
Теорія
Ідея – бульбашка повітря в стакані води піднімається з дна вгору. Тобто найменший ("легкий") елемент переміщується вгору ("спливає"). А точніше, найбільший елемент опускається донизу.
Алгоритм
1.Порівнюємо два сусідніх елементи
2.Якщо вони стоять не в порядку зростання, то переставляємо їх
3.Повторюємо, поки всі елементи не стануть на свої місця
Для сортування масиву з N елементів потрібен N-1 прохід , тобто достатньо поставити на свої місця N-1 елемент.
Відео
Приклад
Задано масив а із n натуральних чисел, впорядкуйте його за допомогою сортування бульбашкою
n = int(input())
a =list(map(int,input().split()))
for i in range(n-1):
for j in range(n-i-1):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
print(*a)
Фрагмент алгоритму через while
i = 0
while i < N - 1:
j = 0
while j < N - 1 - i:
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
j += 1
i += 1
Сортування змішуванням
(англ. Cocktail sort) — один із різновидів алгоритму сортування бульбашкою. Відрізняється від сортування бульбашкою тим, що сортування відбувається в обох напрямках, міняючи напрямок при кожному проході. Цей алгоритм лише трішки складніший за сортування бульбашкою, однак, вирішує так звану проблему «черепах».
Ефективність алгоритму рівна O(n^2) водночас для середнє статистичного та найгіршого випадку, однак, вона прямує доO(n) якщо список вже не погано відсортований, наприклад, якщо кожен елемент знаходиться у позиції, яка відрізняється від кінцевої більше, ніж на k (k ≥ 1), то його швидкодія рівна O(k*n).
Відмінності від сортування бульбашкою
Сортування змішуванням мало чим відрізняється від сортування бульбашкою. Єдина його відмінність у тому, що замість багаторазового проходження через список знизу вгору, він проходить по черзі знизу вгору і згори вниз. Він може досягати трохи вищої ефективності, ніж алгоритм сортування бульбашкою. Причиною цьому є те, що алгоритм сортування бульбашкою проходить по списку лише в одному напрямку, а тому за одну ітерацію елементи списку можна перемістити лише на один крок.
Наприклад, для того, щоб відсортувати список (2,3,4,5,1), алгоритму сортування змішуванням достатньо лише одного проходу, у той час, як алгоритму сортування бульбашкою знадобиться чотири проходи. Однак, один прохід сортування змішуванням слід рахувати за два проходи сортування бульбашкою. Зазвичай, сортування змішуванням удвічі швидше за сортування бульбашкою.
Іншою можливою оптимізацією є запам'ятовування попередніх перестановок. У наступній ітерації, перестановки не повторюватимуться, а тому алгоритм матиме коротші проходи по списку.
Функція сортування змішуванням
def cocktail_sort(A):
for k in range(len(A)-1, 0, -1):
swapped = False
for i in range(k, 0, -1):
if A[i]<A[i-1]:
a = A[i]
b = A[i-1]
A[i] = b
A[i-1] = a
swapped = True
for i in range(k):
if A[i] > A[i+1]:
a = A[i]
b = A[i+1]
A[i] = b
A[i+1] = a
swapped = True
if not swapped:
return A