Алгоритми упорядкування: сортування бульбашкою
Сортування
Впорядковані дані легше шукати (двійковий пошук), порівнювати, подавати в таблицях.
Метод бульбашки
Порівнюємо сусідні елементи й міняємо їх місцями, якщо порядок неправильний. Після кожного проходу найбільший елемент «спливає» в кінець, як бульбашка.
Список [5, 2, 4, 1]:
Прохід | Список після проходу |
|---|---|
1 |
|
2 |
|
3 |
|
Код
a = [5, 2, 4, 1]
n = len(a)
for p in range(n - 1):
for i in range(n - 1 - p):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
print(a) # [1, 2, 4, 5]Для сортування за спаданням змініть > на <.
Оптимізація
Якщо під час проходу жодного обміну не було — список уже впорядкований, можна завершити.
Скільки порівнянь
Для n елементів: (n−1) + (n−2) + … + 1 = n(n−1)/2. Для 10 елементів — 45 порівнянь, для 100 — 4950.
Візуалізатор
Подивіться, як працює бульбашка, у візуалізаторі сортування нижче: порівняння й обміни підсвічуються.
Перевірте себе
Що відбувається з найбільшим елементом після першого проходу?
Скільки порівнянь зробить бульбашка для 6 елементів?
Як зупинити алгоритм раніше, якщо список уже впорядкований?