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

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

Швидке сортування
Алгоритм у дії під час сортування списку чисел.
Основні відомості
Клас: Алгоритм сортування Структура даних: Різні Швидкодія: O(nlogn) Простір: Залежить від реалізації Оптимальний: Інколи

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

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

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

Зміст 1 Історія 2 Псевдокод алгоритму 2.1 Класичний алгоритм 2.2 Сучасний алгоритм 3 Аналіз 3.1 Найгірше розбиття 3.2 Найкраще розбиття 3.3 Середній випадок 4 Модифікації 4.1 Рандомізованний алгоритм 5 Реалізації на різних мовах програмування 5.1 Псевдокод 6 Примітки 7 Джерела інформації 8 Дивіться також 9 Зовнішні посилання

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

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

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

Ця стаття потребує переробки. Прохання поліпшити її, згідно Довідка:Досконала стаття.

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

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

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

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

[ред.] Найгірше розбиття

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

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

[ред.] Найкраще розбиття

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

Тоді:

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

[ред.] Середній випадок

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

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

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

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

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

1 
2 Поміняти 
9 return 

1 if  return;
2 
3 
4 

[ред.] Реалізації на різних мовах програмування

[ред.] Псевдокод

 function QuickSort(Array, Left, Right)
 var
     L2, R2, PivotValue
 begin
     Stack.Push(Left, Right);       // pushes Left, and then Right, on to a stack
     while not Stack.Empty do
     begin
         Stack.Pop(Left, Right);    // pops 2 values, storing them in Right and then Left
         repeat
             PivotValue := Array[(Left + Right) div 2];
             L2 := Left;
             R2 := Right;
             repeat
                 while Array[L2] < PivotValue do // scan left partition
                     L2 := L2 + 1;
                 while Array[R2] > PivotValue do // scan right partition
                     R2 := R2 - 1;
                 if L2 <= R2 then
                 begin
                     if L2 != R2 then
                         Swap(Array[L2], Array[R2]);  // swaps the data at L2 and R2
                     L2 := L2 + 1;
                     R2 := R2 - 1;
                 end;
             until L2 >= R2;
             if R2 - Left > Right - L2 then // is left side piece larger?
             begin
                 if Left < R2 then
                     Stack.Push(Left, R2);
                 Left := L2;
             end;
             else
             begin
                 if L2 < Right then // if left side isn't, right side is larger
                     Stack.Push(L2, Right);
                 Right := R2;
             end;
         until Left >= Right;
     end;
 end;

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

[ред.] Джерела інформації

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

[ред.] Дивіться також

• Список алгоритмів.

[ред.] Зовнішні посилання

• Animated Sorting Algorithms: Quick Sort – графічна демонстрація роботи алгоритму
• Animated Sorting Algorithms: 3-Way Partition Quick Sort – графічна демонстрація трьох прикладів роботи алгоритму
• Interactive Tutorial for Quicksort
• Analyze Quicksort in an online Javascript IDE
• Javascript Quicksort and Bubblesort
• Quicksort applet
• Multidimensional quicksort in Java
• Literate implementations of Quicksort in various languages
• Quicksort tutorial with illustrated examples
• A colored graphical Java applet

п • о • р Алгоритми сортування Теорія Обчислювальна складність | Нотація великого О | Відношення порядку | Список | Стабільність | Сортування на основі порівнянь Сортування обміном Сортування бульбашкою | Сортування змішуванням | Odd-even sort | Сортування гребінцем | Сортування гнома | Швидке сортування Сортування вибором Сортування вибором | Пірамідальне сортування Сортування включенням Сортування включенням | Сортування Шелла | Сортування бінарним деревом | Сортування вставкою з проміжками | Patience sorting Сортування злиттям Сортування злиттям | Strand sort Алгоритми без порівнянь Сортування за розрядами | Сортування комірками | Сортування підрахунком | Цифрове сортування | Burstsort | Bead sort Інші Топологічне сортування | Sorting network | Bitonic sorter Непрактичні алгоритми Сортування Бого | Stooge sort