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