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

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

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

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

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

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

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

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

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

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

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

${\displaystyle T(n)\leq 2T(n/2)+\Theta (n)}$

Тоді:

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

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

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

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

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