streamalism.org

1. Prehľad

V tomto výučbe podrobne preskúmame algoritmus QuickSort so zameraním na jeho implementáciu v prostredí Java.

Budeme tiež diskutovať o jeho výhodách a nevýhodách a potom analyzujeme jeho časovú zložitosť.

2. Algoritmus QuickSort

Quicksort je algoritmus triedenia, ktorý využíva princíp rozdeľuj a panuj. Má priemer O (n log n) zložitosť a je to jeden z najpoužívanejších algoritmov triedenia, najmä pre veľké objemy dát.

Je dôležité mať na pamäti, že Quicksort nie je stabilný algoritmus. Stabilný algoritmus triedenia je algoritmus, v ktorom sa prvky s rovnakými hodnotami objavujú v rovnakom poradí v triedenom výstupe, ako sa vyskytujú vo vstupnom zozname.

Vstupný zoznam je rozdelený na dva podzoznamy prvkom nazývaným pivot; jeden podzoznam s prvkami menšími ako otočný čap a ďalší s podskupinami s prvkami väčšími ako otočný čap. Tento proces sa opakuje pre každý podzoznam.

Nakoniec sa všetky zoradené podzoznamy zlúčia a vytvoria konečný výstup.

2.1. Kroky algoritmu

1. Vyberieme prvok zo zoznamu, ktorý sa nazýva pivot. Použijeme ho na rozdelenie zoznamu na dva podzoznamy.
2. Usporiadame usporiadanie všetkých prvkov okolo otočného čapu - tie, ktoré majú menšiu hodnotu, sú umiestnené pred ním a všetky prvky väčšie ako otočný čap po ňom. Po tomto kroku je čap vo svojej konečnej polohe. Toto je dôležitý krok rozdelenia.
3. Vyššie uvedené kroky rekurzívne použijeme na oba podzoznamy vľavo a vpravo od otočného čepu.

Ako vidíme, quicksort je prirodzene rekurzívny algoritmus, ako každý prístup rozdelenia a panovania.

Urobme si jednoduchý príklad, aby sme tomuto algoritmu lepšie porozumeli.

Arr [] = {5, 9, 4, 6, 5, 3}

1. Predpokladajme, že pre jednoduchosť vyberieme 5 ako otočný čap
2. Najskôr dáme všetky prvky na menej ako 5 na prvú pozíciu poľa: {3, 4, 5, 6, 5, 9}
3. Potom to zopakujeme pre ľavé čiastkové pole {3,4}, pričom ako otočný čap vezmeme 3
4. Neexistujú žiadne prvky menšie ako 3
5. Aplikujeme quicksort na čiastkové pole vpravo od otočného bodu, t. J. {4}
6. Toto čiastkové pole sa skladá iba z jedného triedeného prvku
7. Pokračujeme pravou časťou pôvodného poľa, {6, 5, 9}, až kým nezískame konečné zoradené pole

2.2. Výber optimálneho čapu

Kľúčovým bodom v programe QuickSort je výber najlepšieho otočného čapu. Stredný prvok je samozrejme najlepší, pretože by rozdelil zoznam na dva rovnaké čiastkové zoznamy.

Nájsť prostredný prvok z neusporiadaného zoznamu je ale ťažké a časovo náročné, preto považujeme za otočný prvý prvok, posledný prvok, medián alebo akýkoľvek iný náhodný prvok.

3. Implementácia v Jave

Prvá metóda je quickSort () ktorý berie ako parametre pole na triedenie, prvý a posledný index. Najskôr skontrolujeme indexy a pokračujeme, iba ak ešte existujú prvky na triedenie.

Získame index zoradeného pivotu a použijeme ho na rekurzívne volanie oddiel () metóda s rovnakými parametrami ako quickSort () metóda, ale s rôznymi indexmi:

public void quickSort (int arr [], int begin, int end) {if (begin <end) {int partitionIndex = partition (arr, begin, end); quickSort (arr, begin, partitionIndex-1); quickSort (arr, partitionIndex + 1, koniec); }}

Pokračujme oddiel () metóda. Pre zjednodušenie táto funkcia berie ako otočný prvok posledný prvok. Potom skontroluje každý prvok a zamení ho pred pivotom, ak je jeho hodnota menšia.

Na konci rozdelenia sú všetky prvky menšie ako čap naľavo od neho a všetky prvky väčšie ako čap sú napravo od neho. Pivot je na svojej konečnej zoradenej polohe a funkcia vráti túto pozíciu:

súkromný int oddiel (int arr [], int začiatok, int koniec) {int pivot = arr [end]; int i = (začiatok-1); for (int j = begin; j <end; j ++) {if (arr [j] <= pivot) {i ++; int swapTemp = arr [i]; arr [i] = arr [j]; arr [j] = swapTemp; }} int swapTemp = arr [i + 1]; arr [i + 1] = arr [koniec]; arr [end] = swapTemp; návrat i + 1; }

4. Analýza algoritmov

4.1. Časová zložitosť

V najlepšom prípade algoritmus rozdelí zoznam na dva podzoznamy rovnakej veľkosti. Takže prvá iterácia úplnej verzie n-potrebný zoznam O (n). Zvyšné dva podzoznamy sa triedia podľa n / 2 prvky berie 2 * O (n / 2) každý. Vo výsledku má algoritmus QuickSort zložitosť O (n log n).

V najhoršom prípade vyberie algoritmus v každej iterácii iba jeden prvok O (n) + O (n-1) + ... + O (1), ktorá sa rovná O (n2).

V priemere má QuickSort O (n log n) zložitosť, takže je vhodný pre veľké objemy dát.

4.2. QuickSort vs MergeSort

Poďme diskutovať, v ktorých prípadoch by sme si mali zvoliť QuickSort pred MergeSort.

Aj keď programy Quicksort aj Mergesort majú priemernú časovú zložitosť O (n log n), Quicksort je preferovaný algoritmus, pretože má O (log (n)) zložitosť priestoru. Na druhej strane Mergesort vyžaduje O (n) extra úložisko, čo je pre polia dosť drahé.

Quicksort vyžaduje pre svoju činnosť prístup k rôznym indexom, ale tento prístup nie je priamo možný v prepojených zoznamoch, pretože tu nie sú žiadne súvislé bloky; preto pre prístup k prvku musíme iterovať cez každý uzol od začiatku prepojeného zoznamu. Mergesort je tiež implementovaný bez ďalšieho priestoru pre server LinkedLists.

V takom prípade sa všeobecne uprednostňuje zvýšenie réžie pre Quicksort a Mergesort.

5. Záver

Quicksort je elegantný algoritmus triedenia, ktorý je vo väčšine prípadov veľmi užitočný.

Je to všeobecne algoritmus „na mieste“ s priemernou časovou zložitosťou O (n log n).

Ďalším zaujímavým bodom, ktorý treba spomenúť, je Java Arrays.sort () metóda používa Quicksort na triedenie polí primitívov. Implementácia využíva dva otočné čepy a funguje oveľa lepšie ako naše jednoduché riešenie, preto je pre produkčný kód zvyčajne lepšie používať knižničné metódy.

Ako vždy, kód na implementáciu tohto algoritmu nájdete v našom úložisku GitHub.