Швидке сортування
З Вікіпедії, безкоштовно encyclopedia
Швидке сортування (англ. Quick Sort) — алгоритм сортування, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.
алгоритм у дії під час сортування списку чисел | |
Клас | Алгоритм сортування |
---|---|
Структура даних | Різні |
Найгірша швидкодія | |
Найкраща швидкодія | |
Середня швидкодія | |
Просторова складність у найгіршому випадку | Залежить від реалізації |
Оптимальний | Інколи |
Стабільний | Ні |
Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку.
Швидке сортування є алгоритмом на основі порівнянь і не є стабільним.