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

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

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

У класичному варіанті, запропонованому Гоаром,^[2] з масиву обирали один елемент, а весь масив розбивали на дві частини за принципом: у першій частині — не більші за даний елемент, в другій — не менші за даний елемент. Процедура ${\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}$  do6       repeat7             ${\displaystyle i\gets \;i+1}$ 8       until ${\displaystyle A[i]\geq \;r}$ 9       repeat10            ${\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)}$ 

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

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

${\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     then6           ${\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)}$ 

Ця процедура, після її оголошення, сортує масив 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;

Ця функція сортує масив 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); }

Функція 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]

Метод 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]

• Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Вступ до алгоритмів (вид. 3). К.І.С. ISBN 978-617-684-239-2. {{cite book}}: Cite має пустий невідомий параметр: |1= (довідка)

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

• Реалізація алгоритму швидкого сортування різними мовами програмування [Архівовано 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.]
• Analyze Quicksort in an online Javascript IDE
• Javascript Quicksort and Bubblesort
• Quicksort applet
• Multidimensional quicksort in Java
• Quicksort tutorial with illustrated examples