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

Швидке сортування
Алгоритм у дії під час сортування списку чисел.
Основні відомості
Клас: Алгоритм сортування Структура даних: Різні Швидкодія: O(nlog n) Простір: Залежить від реалізації Оптимальний: Інколи

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

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

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

Історія

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

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

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

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

$\;Quicksort(A,p,q)\;$
1 if $p \ge\; 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]\ge\;r$ 
9       repeat
10            $j\gets\;j-1$ 
11      until $A[j]\le\;r$ 
12      if $\;i<j$ 
13         then Поміняти $A[i]\leftrightarrow\;A[j]$ 
14 $\;Quicksort(A,p,j)$ 
15 $\;Quicksort(A,j+1,q)$ 

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

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

$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]\le\;x\;$
5     then $i\gets\;i+1$
6          Поміняти $A[i]\leftrightarrow\;A[j]$
7 $i\gets\;i+1$
8 Поміняти $A[i]\leftrightarrow\;A[q]$
9 return $\;i$

$Quicksort(A,p,q)\;$
1 if $p \ge\; 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) \le 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 \ge\; q$ return;
2 $i\gets\;Randomized\_Partition(A,p,q)$
3 $\;Randomized\_Quicksort(A,p,i-1)$
4 $\;Randomized\_Quicksort(A,i+1,q)$

Реалізації на різних мовах програмування

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

 function QuickSort(Array, Left, Right)
 var
     L2, R2, PivotValue
 begin
     Stack.Push(Left, Right);       // pushes Left, and then Right, on to a stack
     while not Stack.Empty do
     begin
         Stack.Pop(Left, Right);    // pops 2 values, storing them in Right and then Left
         repeat
             PivotValue := Array[(Left + Right) div 2];
             L2 := Left;
             R2 := Right;
             repeat
                 while Array[L2] < PivotValue do // scan left partition
                     L2 := L2 + 1;
                 while Array[R2] > PivotValue do // scan right partition
                     R2 := R2 - 1;
                 if L2 <= R2 then
                 begin
                     if L2 != R2 then
                         Swap(Array[L2], Array[R2]);  // swaps the data at L2 and R2
                     L2 := L2 + 1;
                     R2 := R2 - 1;
                 end;
             until L2 >= R2;
             if R2 - Left > Right - L2 then // is left side piece larger?
             begin
                 if Left < R2 then
                     Stack.Push(Left, R2);
                 Left := L2;
             end;
             else
             begin
                 if L2 < Right then // if left side isn't, right side is larger
                     Stack.Push(L2, Right);
                 Right := R2;
             end;
         until Left >= Right;
     end;
 end;

Программа на Pascal

 program Quick_Sort; 
  var A:array[1..100] of integer; 
  N,i : integer; 
  {У процедуру передаються ліва та права границі фрагменту, що сортується} 
 procedure QSort(L,R:integer); 
  var X,y,i,j:integer; 
 begin 
  X:=A[(L+R) div 2]; 
  i:=L; j:=R; 
  while i<=j do 
   begin 
    while A[i]<X do i:=i+1; 
    while A[j]>X do j:=j-1; 
      if i<=j then 
        begin 
          y:=A[i]; A[i]:=A[j]; A[j]:=y; 
          i:=i+1; j:=j-1; 
        end; 
   end; 
   if L<j then QSort(L,j); 
   if i<R then QSort(i,R); 
 end; 
 begin 
  write('Кількисть елементів масиву '); 
  read(N); 
  for i:=1 to n do read(A[i]); 
  QSort(1,n); {Впорядкувати елементи з першого по n-ний} 
  for i:=1 to n do write(A[i],' '); {Упорядкований масив} 
 end.

Джерела інформації

• Thimas 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
• Literate implementations of Quicksort in various languages
• Quicksort tutorial with illustrated examples
• A colored graphical Java applet