Алгоритми упорядкування: сортування бульбашкою

Стрілки або пробіл — перемикання · F — повний екран · T — проєкторна тема · ? — підказка

Сортування

Впорядковані дані легше шукати (двійковий пошук), порівнювати, подавати в таблицях.

Метод бульбашки

Порівнюємо сусідні елементи й міняємо їх місцями, якщо порядок неправильний. Після кожного проходу найбільший елемент «спливає» в кінець, як бульбашка.

Список [5, 2, 4, 1]:

Прохід

Список після проходу

1

[2, 4, 1, 5]

2

[2, 1, 4, 5]

3

[1, 2, 4, 5]

Код

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.

Візуалізатор

Подивіться, як працює бульбашка, у візуалізаторі сортування нижче: порівняння й обміни підсвічуються.

Перевірте себе

  1. Що відбувається з найбільшим елементом після першого проходу?

  2. Скільки порівнянь зробить бульбашка для 6 елементів?

  3. Як зупинити алгоритм раніше, якщо список уже впорядкований?

✕ Вийти 1 / 1