Сортування бульбашкою
Знову й знову проходить список і міняє місцями сусідів, що стоять не в тому порядку. Після кожного проходу найбільше з решти значень опиняється в кінці.
- найкраща Ω(n)
- середня Θ(n²)
- найгірша O(n²)
- пам'ять O(1)
- стабільне
- без додаткової пам'яті
Що це означає?
- Найкраща: як росте час із розміром списку n, коли вхідні дані для цього алгоритму найлегші.
- Середня: як зазвичай росте час із n. За n² удвічі більше значень - це приблизно вчетверо довше; n log n росте значно повільніше.
- Найгірша: як росте час на найважчих вхідних даних. Важлива, коли швидкість ніколи не має падати.
- Пам'ять: скільки додаткової пам'яті потрібно, крім списку. 1 - кілька змінних, n - копія списку.
- Стабільне: два рівні значення зберігають свій початковий порядок. Важливо, коли сортуємо записи за одним полем.
- Без додаткової пам'яті: сортує всередині самого списку, без другого списку.
- порівняння
- переміщення
- на остаточному місці
Натисніть «Відтворити»: лінії показують, як росте вартість сортування
Натисніть «Відтворити» або проходьте алгоритм крок за кроком.
Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.
Спробуйте: Оберіть майже відсортований список. Після проходу без жодного обміну алгоритм зупиняється раніше.
Як це працює
Порівнює два сусідні значення і міняє їх місцями, якщо ліве більше. Тож за кожен прохід найбільше значення доходить аж до правого краю, наче бульбашка, що спливає. Якщо за прохід не було жодного обміну, список уже відсортований.
Коли варто використовувати
У реальних програмах майже ніколи, бо на довгих списках воно повільне. Зате добре підходить для навчання: показує саму ідею сортування через порівняння й обміни. Швидке воно лише тоді, коли список уже відсортований.