Швидке сортування

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

найкраща Ω(n log n)
середня Θ(n log n)
найгірша O(n²)
пам'ять O(log n)
нестабільне
без додаткової пам'яті

Що це означає?

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

порівняння
переміщення
опорний елемент
на остаточному місці

0 / 187 кроків

Порівняння Обміни

Натисніть «Відтворити»: лінії показують, як росте вартість сортування

Швидкість 8 кроків/с

Пробіл: відтворення або пауза. Стрілки ліворуч і праворуч: крок. Home і End: на початок або в кінець.

Спробуйте: Оберіть зворотний список. Опорний елемент завжди найменший або найбільший із решти, тож одна частина порожня, а вартість росте до n².

Як це працює

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

Коли варто використовувати

На практиці один із найшвидших способів сортувати, і додаткової пам'яті майже не потребує. Але якщо опорний елемент щоразу поганий, наприклад на вже відсортованому списку, сортування стає повільним. Тому на практиці опорний елемент обирають ретельніше.