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

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

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

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

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

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

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

Ця стаття потребує упорядкування для відповідності стандартам якості Вікіпедії. Будь ласка, допоможіть поліпшити цю статтю. Можливо, сторінка обговорення містить зауваження щодо потрібних змін. (Дізнайтеся, як і коли вилучати це шаблонне повідомлення[en])

У класичному варіанті, запропонованому Гоаром,^[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}$ 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)}$

Нині в стандартних бібліотеках використовують таку реалізацію алгоритму^[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     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)}$

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (жовтень 2016)

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

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (травень 2021)

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

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

• Реалізація алгоритму швидкого сортування різними мовами програмування [Архівовано 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