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

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

алгоритм у дії під час сортування списку чисел
Клас	Алгоритм сортування
Структура даних	Різні
Найгірша швидкодія	$O(n^{2})$$O(n^{2})$
Найкраща швидкодія	$O(n\log n)$$O(n\log n)$
Середня швидкодія	$O(n\log n)$$O(n\log n)$
Просторова складність у найгіршому випадку	Залежить від реалізації
Оптимальний	Інколи
Стабільний	Ні

Швидке сортування (англ. Quick Sort) — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Гоаром, який не потребує додаткової пам'яті і виконує у середньому $\;O(n\log \;n)$$\;O(n\log \;n)$ операцій. Однак, у найгіршому випадку робить $O(n^{2})$$O(n^{2})$ порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.

Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку.

Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.

Історія

Алгоритм швидкого сортування було розроблено Тоні Гоаром (C. A. R. Hoare) у 1962 під час роботи у маленькій британській компанії Elliott Brothers.

Псевдокод алгоритму

Класичний алгоритм

В класичному варіанті, запропонованому Гоаром, з масиву обирався один елемент, і весь масив розбивався на дві частини по принципу: в першій частині — ті що не більші даного елементу, в другій частині — ті що не менші даного елемента. Процедура $Quicksort(A,p,q)$$Quicksort(A,p,q)$ здійснює часткове впорядкування масиву $\;A$$\;A$ з p-го по q-ий індекс:

$\;Quicksort(A,p,q)\;$$\;Quicksort(A,p,q)\;$
1 if $p\geq \;q$$p\geq \;q$ return;
2 $r\gets \;A[p]$$r\gets \;A[p]$ 
3 $i\gets \;p-1$$i\gets \;p-1$ 
4 $j\gets \;q+1$$j\gets \;q+1$ 
5 while $\;i<j$$\;i<j$  do
6       repeat
7             $i\gets \;i+1$$i\gets \;i+1$ 
8       until $A[i]\geq \;r$$A[i]\geq \;r$ 
9       repeat
10            $j\gets \;j-1$$j\gets \;j-1$ 
11      until $A[j]\leq \;r$$A[j]\leq \;r$ 
12      if $\;i<j$$\;i<j$ 
13         then Поміняти $A[i]\leftrightarrow \;A[j]$$A[i]\leftrightarrow \;A[j]$ 
14 $\;Quicksort(A,p,j)$$\;Quicksort(A,p,j)$ 
15 $\;Quicksort(A,j+1,q)$$\;Quicksort(A,j+1,q)$ 

Сучасний алгоритм

Нині в стандартних бібліотеках використовують таку реалізацію алгоритму:

$Partition(A,p,q)\;$$Partition(A,p,q)\;$
1 $x\gets \;A[q]$$x\gets \;A[q]$
2 $i\gets \;p-1$$i\gets \;p-1$
3 for $j\gets \;p$$j\gets \;p$ to $\;q-1$$\;q-1$ 
4 do  if $A[j]\leq \;x\;$$A[j]\leq \;x\;$
5     then
6           $i\gets \;i+1$$i\gets \;i+1$
7           Поміняти $A[i]\leftrightarrow \;A[j]$$A[i]\leftrightarrow \;A[j]$
8 Поміняти $A[i+1]\leftrightarrow \;A[q]$$A[i+1]\leftrightarrow \;A[q]$
8 return $\;i+1$$\;i+1$

Функція Partition повертає індекс з опорним елементом, що розділяє масив на дві частини; ліву - елементи якої менше опорного елементу, і праву - елементи якої більше опорного елементу. Всередині функції опорним елементом вибирається останній елемент масиву і обхід здійснюється починаючи з першого елементу, прирівнюючи його до опорного.

$Quicksort(A,p,q)\;$$Quicksort(A,p,q)\;$
1 if $p\geq \;q$$p\geq \;q$ return;
2 $i\gets \;Partition(A,p,q)$$i\gets \;Partition(A,p,q)$
3 $\;Quicksort(A,p,i-1)$$\;Quicksort(A,p,i-1)$
4 $\;Quicksort(A,i+1,q)$$\;Quicksort(A,i+1,q)$

Аналіз

Час роботи алгоритму сортування залежить від збалансованості, що характеризує розбиття. Збалансованість, у свою чергу залежить від того, який елемент обрано як опорний (відносно якого елемента виконується розбиття). Якщо розбиття збалансоване, то асимптотично алгоритм працює так само швидко як і алгоритм сортування злиттям. У найгіршому випадку, асимптотична поведінка алгоритму настільки ж погана, як і в алгоритму сортування включенням.

Найгірше розбиття

Найгірша поведінка має місце у тому випадку, коли процедура, що виконує розбиття, породжує одну підзадачу з n-1 елементом, а другу — з 0 елементами. Нехай таке незбалансоване розбиття виникає при кожному рекурсивному виклику. Для самого розбиття потрібен час $\;\Theta (n)$$\;\Theta (n)$. Тоді, рекурентне співвідношення для часу роботи, можна записати так:

$\;T(n)=T(n-1)+T(0)+\Theta (n)=T(n-1)+\Theta (n)$$\;T(n)=T(n-1)+T(0)+\Theta (n)=T(n-1)+\Theta (n)$

Розв'язком такого співвідношення є $\;T(n)=\Theta (n^{2})$$\;T(n)=\Theta (n^{2})$.

Найкраще розбиття

В найкращому випадку процедура Partition ділить задачу на дві підзадачі, розмір кожної не перевищує n/2. Час роботи, описується нерівністю:

$T(n)\leq 2T(n/2)+\Theta (n)$$T(n)\leq 2T(n/2)+\Theta (n)$

Тоді:

$\;T(n)=O(n\log n)$$\;T(n)=O(n\log n)$ — асимптотично найкращий час.

Середній випадок

Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є $\;O(n\log n)$$\;O(n\log n)$, тобто середній випадок ближчий до найкращого.

Модифікації

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

Рандомізованний алгоритм

В рандомізованному алгоритмі, при кожному розбитті випадковий елемент обирається як опорний:

$Randomized\_Partition(A,p,q)\;$$Randomized\_Partition(A,p,q)\;$
1 $i\leftarrow Random(p,q)$$i\leftarrow Random(p,q)$
2 Поміняти $A[i]\leftrightarrow A[q]$$A[i]\leftrightarrow A[q]$
9 return $\;Partition(A,p,q)$$\;Partition(A,p,q)$

$Randomized\_Quicksort(A,p,q)\;$$Randomized\_Quicksort(A,p,q)\;$
1 if $p\geq \;q$$p\geq \;q$ return;
2 $i\gets \;Randomized\_Partition(A,p,q)$$i\gets \;Randomized\_Partition(A,p,q)$
3 $\;Randomized\_Quicksort(A,p,i-1)$$\;Randomized\_Quicksort(A,p,i-1)$
4 $\;Randomized\_Quicksort(A,i+1,q)$$\;Randomized\_Quicksort(A,i+1,q)$

Література

• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms (2nd ed.) The MIT Press. ISBN 0-07-013151-1

Див. також

• Список алгоритмів.

Посилання

• Реалізація алгоритму швидкого сортування різними мовами програмування
• Реалізації алгоритму швидкого сортування різними мовами програмування в стилі грамотного програмування
• 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