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

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

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

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

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

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

Алгоритм швидкого сортування було розроблено Тоні Гоаром у 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;

Реалізація мовою C++[ред. | ред. код]

Ця функція сортує масив array, що містить n елементів, де right = n-1.

right-left+1: +1 для того, аби у виклику QuickSort (array, 0, 1) опорним елементом вибирався правий елемент, що не допустить спробу декрементувати j, коли ця змінна вже рівна 0.

 template <typename T>
 void QuickSort (T array[],
                 size_t const left,
                 size_t const right)
 {

     static T temp;
     size_t i=left, j=right;
     T pivot = array[left + ((right-left+1) >> 1)];

     while (i <= j)
     {
         while (array[i] < pivot) ++i;
         while (array[j] > pivot) --j;

         if (i <= j)
         {
             temp = array[i];
             array[i] = array[j];
             array[j] = temp;
             ++i;
             --j;
         }
     }
     if (j > left)
         QuickSort (array, left, j);
     if (i < right)
         QuickSort (array, i, right);
 }

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

  1. Timeline of Computer History: 1960. Computer History Museum. Архів оригіналу за 2013-06-25. Процитовано 2009-01-05. 
  2. Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 7: Швидке сортування. Вступ до алгоритмів (вид. 3). К.І.С. с. 186–206. ISBN 978-617-684-239-2. 

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

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

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