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

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

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

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

 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;

Програма на Pascal[ред.ред. код]

  program Quick_Sort; 
   var A:array[1..100] of integer; 
   N,i : integer; 
   {У процедуру передаються ліва та права границі фрагменту, що сортується} 
  procedure QSort(L,R:integer); 
  var X,y,i,j:integer; 
  begin 
   X:=A[(L+R) div 2]; 
   i:=L; j:=R; 
   while i<=j do 
    begin 
     while A[i]<X do i:=i+1; 
     while A[j]>X do j:=j-1; 
       if i<=j then 
         begin 
           y:=A[i]; A[i]:=A[j]; A[j]:=y; 
           i:=i+1; j:=j-1; 
         end; 
    end; 
    if L<j then QSort(L,j); 
    if i<R then QSort(i,R); 
  end; 
  begin 
   write('Кількість елементів масиву '); 
   read(N); 
   for i:=1 to n do read(A[i]); 
   QSort(1,n); {Впорядкувати елементи з першого по n-ий} 
   for i:=1 to n do write(A[i],' '); {Упорядкований масив} 
  end.

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

  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

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

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