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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Швидке сортування
Sorting quicksort anim.gif
алгоритм у дії під час сортування списку чисел
Клас Алгоритм сортування
Структура даних Різні
Найгірша швидкодія O(n^2)
Найкраща швидкодія O(n\log n)
Середня швидкодія O(n\log n)
Просторова складність у найгіршому випадку Залежить від реалізації
Оптимальний Інколи
Стабільний Ні

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

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

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

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

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

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

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

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

Примітки[ред.ред. код]

  1. «Timeline of Computer History: 1960». Computer History Museum. Архів оригіналу за 2013-06-25. 

Література[ред.ред. код]

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]