Швидке сортування
![]() алгоритм у дії під час сортування списку чисел | |
Клас | Алгоритм сортування |
---|---|
Структура даних | Різні |
Найгірша швидкодія | |
Найкраща швидкодія | |
Середня швидкодія | |
Просторова складність у найгіршому випадку | Залежить від реалізації |
Оптимальний | Інколи |
Стабільний | Ні |
Швидке сортування (англ. Quick Sort) — алгоритм сортування, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.
Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку.
Швидке сортування є алгоритмом на основі порівнянь і не є стабільним.
Історія[ред. | ред. код]
Алгоритм швидкого сортування було розроблено Тоні Гоаром у 1962 під час роботи у маленькій британській компанії Elliott Brothers[en].[1]
Псевдокод алгоритму[ред. | ред. код]
![]() | Ця стаття потребує упорядкування для відповідності стандартам якості Вікіпедії. |
Класичний алгоритм[ред. | ред. код]
В класичному варіанті, запропонованому Гоаром, з масиву обирали один елемент, а весь масив розбивали на дві частини за принципом: у першій частині — не більші за даний елемент, в другій — не менші за даний елемент. Процедура здійснює часткове впорядкування масиву з p-го по q-й індекс:
1 if return; 2 3 4 5 while do 6 repeat 7 8 until 9 repeat 10 11 until 12 if 13 then Поміняти 14 15
Сучасний алгоритм[ред. | ред. код]
Нині в стандартних бібліотеках використовують таку реалізацію алгоритму[2]:
1 2 3 for to 4 do if 5 then 6 7 Swap 8 Swap 8 return
Функція Partition повертає індекс з опорним елементом, що розділяє масив на дві частини; ліву - елементи якої менше опорного елементу, і праву - елементи якої більше опорного елементу. Всередині функції опорним елементом вибирається останній елемент масиву і обхід здійснюється починаючи з першого елементу, прирівнюючи його до опорного.
1 if return; 2 3 4
Аналіз[ред. | ред. код]
Час роботи алгоритму сортування залежить від збалансованості, що характеризує розбиття. Збалансованість, у свою чергу залежить від того, який елемент обрано як опорний (відносно якого елемента виконується розбиття). Якщо розбиття збалансоване, то асимптотично алгоритм працює так само швидко як і алгоритм сортування злиттям. У найгіршому випадку, асимптотична поведінка алгоритму настільки ж погана, як і в алгоритму сортування включенням.
Найгірше розбиття[ред. | ред. код]
Найгірша поведінка має місце у тому випадку, коли процедура, що виконує розбиття, породжує одну підзадачу з n-1 елементом, а другу — з 0 елементами. Нехай таке незбалансоване розбиття виникає при кожному рекурсивному виклику. Для самого розбиття потрібен час . Тоді, рекурентне співвідношення для часу роботи, можна записати так:
Розв'язком такого співвідношення є .
Найкраще розбиття[ред. | ред. код]
В найкращому випадку процедура Partition ділить задачу на дві підзадачі, розмір кожної не перевищує n/2. Час роботи, описується нерівністю:
Тоді:
— асимптотично найкращий час.
Середній випадок[ред. | ред. код]
Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є , тобто середній випадок ближчий до найкращого.
Модифікації[ред. | ред. код]
В середньому алгоритм працює дуже швидко, але на практиці, не всі можливі вхідні масиви мають однакову імовірність. Тоді, шляхом додання рандомізації вдається отримати середній час роботи в будь-якому випадку.
Рандомізованний алгоритм[ред. | ред. код]
В рандомізованному алгоритмі, при кожному розбитті випадковий елемент обирається як опорний:
1 2 Поміняти 9 return
1 if return; 2 3 4
Реалізація мовою Pascal[ред. | ред. код]
![]() | Цей розділ не містить посилань на джерела. (жовтень 2016) |
Ця процедура, після її оголошення, сортує масив mas, який складається з елементів типу integer.
Procedure QuickSort(first, last :integer);
Var v, x, left, right :integer;
begin
left := first;
right := last;
v := mas[(left + right) div 2];
while left <= right do
begin
while mas[left] < v do
left := left + 1;
while mas[right] > v do
right := right - 1;
if left <= right then
begin
x := mas[left];
mas[left] := mas[right];
mas[right] := x;
left := left + 1;
right := right - 1;
end;
end;
if first < right then
QuickSort(first, right);
if left < last then
QuickSort(left, last);
end;
Примітки[ред. | ред. код]
- ↑ Timeline of Computer History: 1960. Computer History Museum. Архів оригіналу за 2013-06-25. Процитовано 2009-01-05.
- ↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). 7.1 Description of quicksort. Introduction to Algorithms (вид. 3-тє). The MIT Press. с. 171. ISBN 978-0-262-03384-8.
Література[ред. | ред. код]
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест. Вступ до алгоритмів. MIT Press і McGraw-Hill.
Див. також[ред. | ред. код]
Посилання[ред. | ред. код]
- Реалізація алгоритму швидкого сортування різними мовами програмування
- Реалізації алгоритму швидкого сортування різними мовами програмування в стилі грамотного програмування
- Animated Sorting Algorithms: Quick Sort — графічна демонстрація роботи алгоритму
- Animated Sorting Algorithms: 3-Way Partition Quick Sort — графічна демонстрація алгоритму швидкого сортування з розбиттям масиву на три частини.
- Наочна демонстрація швидкого сортування угорськими танцюристами.
- Interactive Tutorial for Quicksort
- Analyze Quicksort in an online Javascript IDE
- Javascript Quicksort and Bubblesort
- Quicksort applet
- Multidimensional quicksort in Java
- Quicksort tutorial with illustrated examples
|