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

Матеріал з Вікіпедії — вільної енциклопедії.

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

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

Зміст

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

Алгоритм розробив англійський вчений в області інформатики Чарльз Хоар. Швидке сортування розроблялось для використання при машинному перекладі. На сьогодні, це найбільш популярний алгоритм сортування і він входить до стандартних бібліотек більшості мов програмування.

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

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

В класичному варіанті, запропонованому Хоаром, з масиву обирався один елемент, і весь масив розбивався на дві частини по принцупу: в першій частині — ті що не більші даного елементу, в другій частині — ті що не менші даного елемента. Процедура 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 \;r-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[r]
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)

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

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