Швидке сортування
Швидке сортування (англ. Quick Sort) — алгоритм сортування, розроблений Тоні Гоаром, який не потребує додаткової пам'яті і виконує у середньому операцій. Однак, у найгіршому випадку робить порівнянь. Позаяк алгоритм використовує дуже прості цикли і операції, він працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям. Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку. Швидке сортування є алгоритмом на основі порівнянь і не є стабільним. ІсторіяАлгоритм швидкого сортування було розроблено Тоні Гоаром у 1962 під час роботи у маленькій британській компанії Elliott Brothers[en].[1] Псевдокод алгоритмуКласичний алгоритмУ класичному варіанті, запропонованому Гоаром,[2] з масиву обирали один елемент, а весь масив розбивали на дві частини за принципом: у першій частині — не більші за даний елемент, в другій — не менші за даний елемент. Процедура здійснює часткове впорядкування масиву з 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 Swap 14 15 Сучасний алгоритмНині в стандартних бібліотеках використовують таку реалізацію алгоритму[3]: 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);
}
Реалізація мовою JavaScript[4]Функція 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[5]Метод 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]
Примітки
Література
Посилання
|
Portal di Ensiklopedia Dunia