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

Швидке сортування
	алгоритм у дії під час сортування списку чисел
Клас	Алгоритм сортування
Структура даних	Різні
Найгірша швидкодія
Найкраща швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку	Залежить від реалізації
Оптимальний	Інколи
Стабільний	Ні

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

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

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

Історія[ред. | ред. код]

Алгоритм швидкого сортування було розроблено Тоні Гоаром у 1962 під час роботи у маленькій британській компанії Elliott Brothers^[en].^[1]

Псевдокод алгоритму[ред. | ред. код]

Класичний алгоритм[ред. | ред. код]

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

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

Сучасний алгоритм[ред. | ред. код]

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

 $Partition(A,p,q)\;$ 
1  $x\gets \;A[q]$ 
2  $i\gets \;p-1$ 
3 for  $j\gets \;p$  to  $\;q-1$  
4 do  if  $A[j]\leq \;x\;$ 
5     then
6            $i\gets \;i+1$ 
7           Swap  $A[i]\leftrightarrow \;A[j]$ 
8 Swap  $A[i+1]\leftrightarrow \;A[q]$ 
8 return  $\;i+1$

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

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

Аналіз[ред. | ред. код]

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

Найгірше розбиття[ред. | ред. код]

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

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

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

Найкраще розбиття[ред. | ред. код]

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

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

Тоді:

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

Середній випадок[ред. | ред. код]

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

Модифікації[ред. | ред. код]

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

Рандомізованний алгоритм[ред. | ред. код]

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

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

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

Реалізація мовою Pascal[ред. | ред. код]

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

[1] Timeline of Computer History: 1960. Computer History Museum. Архів оригіналу за 2013-06-25. Процитовано 2009-01-05.

[2] 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.

[1]

[2]