Відкрити головне меню

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

Швидке сортування
Sorting quicksort anim.gif
алгоритм у дії під час сортування списку чисел
Клас Алгоритм сортування
Структура даних Різні
Найгірша швидкодія
Найкраща швидкодія
Середня швидкодія
Просторова складність у найгіршому випадку Залежить від реалізації
Оптимальний Інколи
Стабільний Ні

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

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

ІсторіяРедагувати

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

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

Класичний алгоритмРедагувати

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

Сучасний алгоритмРедагувати

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

 
1  
2  
3 for   to   
4 do  if  
5     then
6            
7           Swap  
8 Swap  
8 return  

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

 
1 if   return;
2  
3  
4  

АналізРедагувати

Час роботи алгоритму сортування залежить від збалансованості, що характеризує розбиття. Збалансованість, у свою чергу залежить від того, який елемент обрано як опорний (відносно якого елемента виконується розбиття). Якщо розбиття збалансоване, то асимптотично алгоритм працює так само швидко як і алгоритм сортування злиттям. У найгіршому випадку, асимптотична поведінка алгоритму настільки ж погана, як і в алгоритму сортування включенням.

Найгірше розбиттяРедагувати

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

 

Розв'язком такого співвідношення є  .

Найкраще розбиттяРедагувати

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

 

Тоді:

  — асимптотично найкращий час.

Середній випадокРедагувати

Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є  , тобто середній випадок ближчий до найкращого.

МодифікаціїРедагувати

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

Рандомізованний алгоритмРедагувати

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

 
1  
2 Поміняти  
9 return  
 
1 if   return;
2  
3  
4  

Реалізація мовою PascalРедагувати

Ця процедура, після її оголошення, сортує масив mas, який складається з елементів типу integer.

Procedure QuickSort(first, last :integer);
Var v, x, left, right :integer;
begin
  left := first;
  right := last;
  v := mas[(left + right) div 2];
  while left <= right do
    begin
    while mas[left] < v do
      left := left + 1;
    while mas[right] > v do
      right := right - 1;
    if left <= right then
      begin
        x := mas[left];
        mas[left] := mas[right];
        mas[right] := x;
        left := left + 1;
        right := right - 1;
      end;
    end;
  if first < right then 
    QuickSort(first, right);
  if left < last then
    QuickSort(left, last);
end;

ПриміткиРедагувати

  1. Timeline of Computer History: 1960. Computer History Museum. Архів оригіналу за 2013-06-25. Процитовано 2009-01-05. 
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). 7.1 Description of quicksort. Introduction to Algorithms (вид. 3-тє). The MIT Press. с. 171. ISBN 978-0-262-03384-8. 

ЛітератураРедагувати

Див. такожРедагувати

ПосиланняРедагувати