Quicksort

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

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

алгоритм у дії під час сортування списку чисел
Клас	Алгоритм сортування
Структура даних	Різні
Найгірша швидкодія	${\displaystyle O(n^{2})}$
Найкраща швидкодія	${\displaystyle O(n\log n)}$
Середня швидкодія	${\displaystyle O(n\log n)}$
Просторова складність у найгіршому випадку	Залежить від реалізації
Оптимальний	Інколи
Стабільний	Ні

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

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

Історія

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

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

Класичний алгоритм

У класичному варіанті, запропонованому Гоаром, з масиву обирали один елемент, а весь масив розбивали на дві частини за принципом: у першій частині — не більші за даний елемент, в другій — не менші за даний елемент. Процедура ${\displaystyle Quicksort(A,p,q)}$ здійснює часткове впорядкування масиву ${\displaystyle \;A}$ з p-го по q-й індекс:

${\displaystyle \;Quicksort(A,p,q)\;}$ 1 if ${\displaystyle p\geq \;q}$ return; 2 ${\displaystyle r\gets \;A[p]}$ 3 ${\displaystyle i\gets \;p-1}$ 4 ${\displaystyle j\gets \;q+1}$ 5 while ${\displaystyle \;i<j}$ do 6 repeat 7 ${\displaystyle i\gets \;i+1}$ 8 until ${\displaystyle A[i]\geq \;r}$ 9 repeat 10 ${\displaystyle j\gets \;j-1}$ 11 until ${\displaystyle A[j]\leq \;r}$ 12 if ${\displaystyle \;i<j}$ 13 then Swap ${\displaystyle A[i]\leftrightarrow \;A[j]}$ 14 ${\displaystyle \;Quicksort(A,p,j-1)}$ 15 ${\displaystyle \;Quicksort(A,j+1,q)}$ 

Сучасний алгоритм

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

${\displaystyle Partition(A,p,q)\;}$ 1 ${\displaystyle x\gets \;A[q]}$ 2 ${\displaystyle i\gets \;p-1}$ 3 for ${\displaystyle j\gets \;p}$ to ${\displaystyle \;q-1}$ 4 do if ${\displaystyle A[j]\leq \;x\;}$ 5 then 6 ${\displaystyle i\gets \;i+1}$ 7 Swap ${\displaystyle A[i]\leftrightarrow \;A[j]}$ 8 Swap ${\displaystyle A[i+1]\leftrightarrow \;A[q]}$ 8 return ${\displaystyle \;i+1}$ 

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

${\displaystyle Quicksort(A,p,q)\;}$ 1 if ${\displaystyle p\geq \;q}$ return; 2 ${\displaystyle i\gets \;Partition(A,p,q)}$ 3 ${\displaystyle \;Quicksort(A,p,i-1)}$ 4 ${\displaystyle \;Quicksort(A,i+1,q)}$ 

Аналіз

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

Найгірше розбиття

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

${\displaystyle \;T(n)=T(n-1)+T(0)+\Theta (n)=T(n-1)+\Theta (n)}$

Розв'язком такого співвідношення є ${\displaystyle \;T(n)=\Theta (n^{2})}$.

Найкраще розбиття

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

${\displaystyle T(n)\leq 2T(n/2)+\Theta (n)}$

Тоді:

${\displaystyle \;T(n)=O(n\log n)}$ — асимптотично найкращий час.

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

Математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах є ${\displaystyle \;O(n\log n)}$, тобто середній випадок ближчий до найкращого.

Модифікації

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

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

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

${\displaystyle Randomized\_Partition(A,p,q)\;}$ 1 ${\displaystyle i\leftarrow Random(p,q)}$ 2 Поміняти ${\displaystyle A[i]\leftrightarrow A[q]}$ 9 return ${\displaystyle \;Partition(A,p,q)}$ 

${\displaystyle Randomized\_Quicksort(A,p,q)\;}$ 1 if ${\displaystyle p\geq \;q}$ return; 2 ${\displaystyle i\gets \;Randomized\_Partition(A,p,q)}$ 3 ${\displaystyle \;Randomized\_Quicksort(A,p,i-1)}$ 4 ${\displaystyle \;Randomized\_Quicksort(A,i+1,q)}$ 

Реалізація мовою 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);  } 

Реалізація мовою JavaScript

Функція quickSort приймає масив arr як вхідний параметр і повертає відсортований масив.

function quickSort(arr) {  if (arr.length <= 1) {  return arr;  }    const pivot = arr[Math.floor(arr.length / 2)];  const less = [];  const greater = [];    for (let i = 0; i < arr.length; i++) {  if (arr[i] < pivot) {  less.push(arr[i]);  } else if (arr[i] > pivot) {  greater.push(arr[i]);  }  }    return [...quickSort(less), pivot, ...quickSort(greater)]; }  // Приклад використання: const array = [5, 3, 1, 6, 2, 4]; const sortedArray = quickSort(array); console.log(sortedArray);  // Результат // [1, 2, 3, 4, 5, 6] 

Реалізація мовою Ruby

Метод quick_sort приймає масив arr як вхідний параметр і повертає відсортований масив.

def quick_sort(arr)  return arr if arr.length <= 1   pivot = arr[arr.length / 2]  less = []  greater = []   arr.each do |element|  if element < pivot  less << element  elsif element > pivot  greater << element  end  end   return [*quick_sort(less), pivot, *quick_sort(greater)] end  # Приклад використання: array = [5, 3, 1, 6, 2, 4] sorted_array = quick_sort(array) puts sorted_array  # Результат # [1, 2, 3, 4, 5, 6] 

Примітки

1. Timeline of Computer History: 1960. Computer History Museum. Архів оригіналу за 25 червня 2013. Процитовано 5 січня 2009.
2. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 7. Швидке сортування. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
3. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 7: Швидке сортування. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
4. Приклад QuickSort алгоритму (JavaScript). tseivo.com. Процитовано 5 липня 2023.
5. Приклад QuickSort алгоритму (Ruby). tseivo.com. Процитовано 5 липня 2023.

Література

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 7 Швидке сортування. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .

Посилання

• Реалізація алгоритму швидкого сортування різними мовами програмування [ 7 лютого 2015 у Wayback Machine.]
• Реалізації алгоритму швидкого сортування різними мовами програмування в стилі грамотного програмування [ 9 травня 2008 у Wayback Machine.]
• Animated Sorting Algorithms: Quick Sort — графічна демонстрація роботи алгоритму
• Animated Sorting Algorithms: 3-Way Partition Quick Sort — графічна демонстрація алгоритму швидкого сортування з розбиттям масиву на три частини.
• Наочна демонстрація швидкого сортування угорськими танцюристами. [ 7 червня 2014 у Wayback Machine.]
• Interactive Tutorial for Quicksort [ 3 лютого 2009 у Wayback Machine.]