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

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

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

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

Зміст 1 Історія 2 Псевдокод алгоритму 2.1 Класичний алгоритм 2.2 Сучасний алгоритм 3 Аналіз 4 Модифікації

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

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

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

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

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

1 if  return;
2 
3 
4 
5 while  do
6       repeat
7             
8       until 
9       repeat
10            
11      until 
12      if 
13         then Поміняти 
14 
15 

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

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

1 
2 
3 for  to  
4 do  if 
5     then 
6          Поміняти 
7 
8 Поміняти 
9 return 

1 if  return;
2 
3 
4 

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

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