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