www.wikidata.uk-ua.nina.az

Швидке сортування англ Quick Sort алгоритм сортування розроблений Тоні Гоаром який не потребує додаткової пам яті і вико

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

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

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

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

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

Історія Редагувати

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

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

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


Класичний алгоритм Редагувати

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

У класичному варіанті, запропонованому Гоаром, з масиву обирали один елемент, а весь масив розбивали на дві частини за принципом: у першій частині — не більші за даний елемент, в другій — не менші за даний елемент. Процедура здійснює часткове впорядкування масиву з 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

Сучасний алгоритм Редагувати

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

 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 Редагувати

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (жовтень 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;

Реалізація мовою C++ Редагувати

Цей розділ не містить посилань на джерела. Ви можете допомогти поліпшити цей розділ, додавши посилання на надійні (авторитетні) джерела. Матеріал без джерел може бути піддано сумніву та вилучено. (травень 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);  }

Реалізація мовою 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. Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 7: Швидке сортування. Вступ до алгоритмів (вид. 3). К.І.С. с. 186–206. ISBN 978-617-684-239-2. 
  3. Приклад QuickSort алгоритму (JavaScript).. tseivo.com. Процитовано 5 липня 2023. 
  4. Приклад QuickSort алгоритму (Ruby).. tseivo.com. Процитовано 5 липня 2023. 

Література Редагувати

Див. також Редагувати

Посилання Редагувати


Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Shvidke sortuvannya angl Quick Sort algoritm sortuvannya rozroblenij Toni Goarom yakij ne potrebuye dodatkovoyi pam yati i vikonuye u serednomu O n log n displaystyle O n log n operacij Odnak u najgirshomu vipadku robit O n 2 displaystyle O n 2 porivnyan Pozayak algoritm vikoristovuye duzhe prosti cikli i operaciyi vin pracyuye shvidshe za inshi algoritmi sho mayut taku zh asimptotichnu ocinku skladnosti Napriklad zazvichaj bilsh nizh udvichi shvidshij porivnyano z sortuvannyam zlittyam Shvidke sortuvannyaalgoritm u diyi pid chas sortuvannya spisku chiselKlas Algoritm sortuvannyaStruktura danih RizniNajgirsha shvidkodiya O n 2 displaystyle O n 2 Najkrasha shvidkodiya O n log n displaystyle O n log n Serednya shvidkodiya O n log n displaystyle O n log n Prostorova skladnist u najgirshomu vipadku Zalezhit vid realizaciyiOptimalnij InkoliStabilnij NiIdeya algoritmu polyagaye v perestavlyanni elementiv masivu takim chinom shob jogo mozhna bulo rozdiliti na dvi chastini i kozhnij element z pershoyi chastini buv ne bilshij za bud yakij element z drugoyi Vporyadkuvannya kozhnoyi z chastin vidbuvayetsya rekursivno Algoritm shvidkogo sortuvannya mozhe buti realizovanij yak u masivi tak i v dvozv yaznomu spisku Shvidke sortuvannya ye algoritmom na osnovi porivnyan i ne ye stabilnim Zmist 1 Istoriya 2 Psevdokod algoritmu 2 1 Klasichnij algoritm 2 2 Suchasnij algoritm 3 Analiz 3 1 Najgirshe rozbittya 3 2 Najkrashe rozbittya 3 3 Serednij vipadok 4 Modifikaciyi 4 1 Randomizovannij algoritm 5 Realizaciya movoyu Pascal 6 Realizaciya movoyu C 7 Realizaciya movoyu JavaScript 3 8 Realizaciya movoyu Ruby 4 9 Primitki 10 Literatura 11 Div takozh 12 PosilannyaIstoriya RedaguvatiAlgoritm shvidkogo sortuvannya bulo rozrobleno Toni Goarom u 1962 pid chas roboti u malenkij britanskij kompaniyi Elliott Brothers en 1 Psevdokod algoritmu RedaguvatiCya stattya potrebuye uporyadkuvannya dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit polipshiti cyu stattyu Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin Klasichnij algoritm Redaguvati Cej rozdil ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cej rozdil dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno sichen 2022 U klasichnomu varianti zaproponovanomu Goarom z masivu obirali odin element a ves masiv rozbivali na dvi chastini za principom u pershij chastini ne bilshi za danij element v drugij ne menshi za danij element Procedura Q u i c k s o r t A p q displaystyle Quicksort A p q nbsp zdijsnyuye chastkove vporyadkuvannya masivu A displaystyle A nbsp z p go po q j indeks Q u i c k s o r t A p q displaystyle Quicksort A p q nbsp 1 if p q displaystyle p geq q nbsp return 2 r A p displaystyle r gets A p nbsp 3 i p displaystyle i gets p nbsp 4 j q 1 displaystyle j gets q 1 nbsp 5 while i lt j displaystyle i lt j nbsp do 6 repeat 7 i i 1 displaystyle i gets i 1 nbsp 8 until A i r displaystyle A i geq r nbsp 9 repeat 10 j j 1 displaystyle j gets j 1 nbsp 11 until A j r displaystyle A j leq r nbsp 12 if i lt j displaystyle i lt j nbsp 13 then Swap A i A j displaystyle A i leftrightarrow A j nbsp 14 Q u i c k s o r t A p j displaystyle Quicksort A p j nbsp 15 Q u i c k s o r t A j 1 q displaystyle Quicksort A j 1 q nbsp Suchasnij algoritm Redaguvati Nini v standartnih bibliotekah vikoristovuyut taku realizaciyu algoritmu 2 P a r t i t i o n A p q displaystyle Partition A p q nbsp 1 x A q displaystyle x gets A q nbsp 2 i p 1 displaystyle i gets p 1 nbsp 3 for j p displaystyle j gets p nbsp to q 1 displaystyle q 1 nbsp 4 do if A j x displaystyle A j leq x nbsp 5 then 6 i i 1 displaystyle i gets i 1 nbsp 7 Swap A i A j displaystyle A i leftrightarrow A j nbsp 8 Swap A i 1 A q displaystyle A i 1 leftrightarrow A q nbsp 8 return i 1 displaystyle i 1 nbsp Funkciya Partition povertaye indeks z opornim elementom sho rozdilyaye masiv na dvi chastini livu elementi yakoyi menshe opornogo elementu i pravu elementi yakoyi bilshe opornogo elementu Vseredini funkciyi opornim elementom vibirayetsya ostannij element masivu i obhid zdijsnyuyetsya pochinayuchi z pershogo elementu pririvnyuyuchi jogo do opornogo Q u i c k s o r t A p q displaystyle Quicksort A p q nbsp 1 if p q displaystyle p geq q nbsp return 2 i P a r t i t i o n A p q displaystyle i gets Partition A p q nbsp 3 Q u i c k s o r t A p i 1 displaystyle Quicksort A p i 1 nbsp 4 Q u i c k s o r t A i 1 q displaystyle Quicksort A i 1 q nbsp Analiz RedaguvatiChas roboti algoritmu sortuvannya zalezhit vid zbalansovanosti sho harakterizuye rozbittya Zbalansovanist u svoyu chergu zalezhit vid togo yakij element obrano yak opornij vidnosno yakogo elementa vikonuyetsya rozbittya Yaksho rozbittya zbalansovane to asimptotichno algoritm pracyuye tak samo shvidko yak i algoritm sortuvannya zlittyam U najgirshomu vipadku asimptotichna povedinka algoritmu nastilki zh pogana yak i v algoritmu sortuvannya vklyuchennyam Najgirshe rozbittya Redaguvati Najgirsha povedinka maye misce u tomu vipadku koli procedura sho vikonuye rozbittya porodzhuye odnu pidzadachu z n 1 elementom a drugu z 0 elementami Nehaj take nezbalansovane rozbittya vinikaye pri kozhnomu rekursivnomu vikliku Dlya samogo rozbittya potriben chas 8 n displaystyle Theta n nbsp Todi rekurentne spivvidnoshennya dlya chasu roboti mozhna zapisati tak T n T n 1 T 0 8 n T n 1 8 n displaystyle T n T n 1 T 0 Theta n T n 1 Theta n nbsp Rozv yazkom takogo spivvidnoshennya ye T n 8 n 2 displaystyle T n Theta n 2 nbsp Najkrashe rozbittya Redaguvati V najkrashomu vipadku procedura Partition dilit zadachu na dvi pidzadachi rozmir kozhnoyi ne perevishuye n 2 Chas roboti opisuyetsya nerivnistyu T n 2 T n 2 8 n displaystyle T n leq 2T n 2 Theta n nbsp Todi T n O n log n displaystyle T n O n log n nbsp asimptotichno najkrashij chas Serednij vipadok Redaguvati Matematichne ochikuvannya chasu roboti algoritmu na vsih mozhlivih vhidnih masivah ye O n log n displaystyle O n log n nbsp tobto serednij vipadok blizhchij do najkrashogo Modifikaciyi RedaguvatiV serednomu algoritm pracyuye duzhe shvidko ale na praktici ne vsi mozhlivi vhidni masivi mayut odnakovu imovirnist Todi shlyahom dodannya randomizaciyi vdayetsya otrimati serednij chas roboti v bud yakomu vipadku Randomizovannij algoritm Redaguvati V randomizovannomu algoritmi pri kozhnomu rozbitti vipadkovij element obirayetsya yak opornij R a n d o m i z e d P a r t i t i o n A p q displaystyle Randomized Partition A p q nbsp 1 i R a n d o m p q displaystyle i leftarrow Random p q nbsp 2 Pominyati A i A q displaystyle A i leftrightarrow A q nbsp 9 return P a r t i t i o n A p q displaystyle Partition A p q nbsp R a n d o m i z e d Q u i c k s o r t A p q displaystyle Randomized Quicksort A p q nbsp 1 if p q displaystyle p geq q nbsp return 2 i R a n d o m i z e d P a r t i t i o n A p q displaystyle i gets Randomized Partition A p q nbsp 3 R a n d o m i z e d Q u i c k s o r t A p i 1 displaystyle Randomized Quicksort A p i 1 nbsp 4 R a n d o m i z e d Q u i c k s o r t A i 1 q displaystyle Randomized Quicksort A i 1 q nbsp Realizaciya movoyu Pascal RedaguvatiCej rozdil ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cej rozdil dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno zhovten 2016 Cya procedura pislya yiyi ogoloshennya sortuye masiv mas yakij skladayetsya z elementiv tipu 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 lt right do begin while mas left lt v do left left 1 while mas right gt v do right right 1 if left lt right then begin x mas left mas left mas right mas right x left left 1 right right 1 end end if first lt right then QuickSort first right if left lt last then QuickSort left last end Realizaciya movoyu C RedaguvatiCej rozdil ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cej rozdil dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno traven 2021 Cya funkciya sortuye masiv array sho mistit n elementiv de right n 1 right left 1 1 dlya togo abi u vikliku QuickSort array 0 1 opornim elementom vibiravsya pravij element sho ne dopustit sprobu dekrementuvati j koli cya zminna vzhe rivna 0 template lt typename T gt 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 gt gt 1 while i lt j while array i lt pivot i while array j gt pivot j if i lt j temp array i array i array j array j temp i j if j gt left QuickSort array left j if i lt right QuickSort array i right Realizaciya movoyu JavaScript 3 RedaguvatiFunkciya quickSort prijmaye masiv arr yak vhidnij parametr i povertaye vidsortovanij masiv function quickSort arr if arr length lt 1 return arr const pivot arr Math floor arr length 2 const less const greater for let i 0 i lt arr length i if arr i lt pivot less push arr i else if arr i gt pivot greater push arr i return quickSort less pivot quickSort greater Priklad vikoristannya const array 5 3 1 6 2 4 const sortedArray quickSort array console log sortedArray Rezultat 1 2 3 4 5 6 Realizaciya movoyu Ruby 4 RedaguvatiMetod quick sort prijmaye masiv arr yak vhidnij parametr i povertaye vidsortovanij masiv def quick sort arr return arr if arr length lt 1 pivot arr arr length 2 less greater arr each do element if element lt pivot less lt lt element elsif element gt pivot greater lt lt element end end return quick sort less pivot quick sort greater end Priklad vikoristannya array 5 3 1 6 2 4 sorted array quick sort array puts sorted array Rezultat 1 2 3 4 5 6 Primitki Redaguvati Timeline of Computer History 1960 Computer History Museum Arhiv originalu za 25 chervnya 2013 Procitovano 5 sichnya 2009 Kormen Tomas Lejzerson Charlz Rivest Ronald Stajn Kliford 2019 Rozdil 7 Shvidke sortuvannya Vstup do algoritmiv vid 3 K I S s 186 206 ISBN 978 617 684 239 2 Priklad QuickSort algoritmu JavaScript tseivo com Procitovano 5 lipnya 2023 Priklad QuickSort algoritmu Ruby tseivo com Procitovano 5 lipnya 2023 Literatura RedaguvatiKormen Tomas Lejzerson Charlz Rivest Ronald Stajn Kliford 2019 Vstup do algoritmiv vid 3 K I S ISBN 978 617 684 239 2 Div takozh RedaguvatiSpisok algoritmivPosilannya RedaguvatiRealizaciya algoritmu shvidkogo sortuvannya riznimi movami programuvannya Arhivovano 7 lyutogo 2015 u Wayback Machine Realizaciyi algoritmu shvidkogo sortuvannya riznimi movami programuvannya v stili gramotnogo programuvannya Arhivovano 9 travnya 2008 u Wayback Machine Animated Sorting Algorithms Quick Sort grafichna demonstraciya roboti algoritmu Animated Sorting Algorithms 3 Way Partition Quick Sort grafichna demonstraciya algoritmu shvidkogo sortuvannya z rozbittyam masivu na tri chastini Naochna demonstraciya shvidkogo sortuvannya ugorskimi tancyuristami Arhivovano 7 chervnya 2014 u Wayback Machine Interactive Tutorial for Quicksort Arhivovano 3 lyutogo 2009 u Wayback Machine Analyze Quicksort in an online Javascript IDE Javascript Quicksort and Bubblesort Quicksort applet Multidimensional quicksort in Java Quicksort tutorial with illustrated examples Otrimano z https uk wikipedia org w index php title Shvidke sortuvannya amp oldid 40487639