Algoritmus QuickSort v JavaScripte

Čo je to rýchle triedenie?

Algoritmus Quick Sort sleduje prístup Divide and Conquer. Rozdeľuje prvky na menšie časti na základe určitých podmienok a vykonávanie triediacich operácií na týchto rozdelených menších častiach.

Algoritmus Quick Sort je jedným z najbežnejších a najpopulárnejších algoritmov v akomkoľvek programovacom jazyku. Ak ste ale vývojárom JavaScriptu, mohli ste počuť o sort (), ktorý je už v JavaScripte k dispozícii. Potom by vás možno napadlo, čo je potrebným pre tento algoritmus rýchleho triedenia. Aby sme to pochopili, najskôr potrebujeme, čo je triedenie a aké je predvolené triedenie v JavaScripte.

Čo je triedenie?

Triedenie nie je nič iné ako, usporiadanie prvkov do požadovaného poradia. Možno ste sa s tým stretli už v školských alebo vysokoškolských časoch. Rovnako ako usporiadanie čísel od menších po väčšie (vzostupne) alebo od väčších po menšie (zostupne) je to, čo sme doteraz videli, a nazýva sa triedenie.

Predvolené triedenie v JavaScripte

Ako už bolo spomenuté, JavaScript má sort () . Vezmime si príklad s niekoľkými radmi prvkov, ako je [5,3,7,6,2,9], a chceme zoradiť tieto prvky poľa vo vzostupnom poradí. Stačí zavolať sort () na pole items a zoradí prvky poľa vo vzostupnom poradí.

Kód:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

Aký je dôvod zvoliť si v JavaScripte rýchle zoradenie pred predvoleným zoradením ()

Aj keď sort () dáva požadovaný výsledok, problém spočíva v spôsobe triedenia prvkov poľa. Predvolené zoradenie () v JavaScripte používa zoradenie vloženia podľa V8 Engine prehliadača Chrome a zlúčenie zoradenia podľa Mozilla Firefox a Safari .

Iné však nie je vhodné, ak potrebujete triediť veľké množstvo prvkov. Riešením je teda použitie rýchleho zoradenia pre veľkú množinu údajov.

Aby ste to úplne pochopili, musíte vedieť, ako funguje rýchle triedenie, a pozrime sa na to teraz podrobne.

Čo je rýchle triedenie?

Rýchle triedenie nasleduje podľa algoritmu Divide and Conquer . Rozdeľuje prvky na menšie časti na základe určitých podmienok a vykonáva operácie triedenia na rozdelených menších častiach. Preto to funguje dobre pre veľké súbory údajov. Tu sú kroky, ako rýchle triedenie funguje jednoduchými slovami.

Najskôr vyberte prvok, ktorý sa má nazývať ako otočný prvok.
Ďalej porovnajte všetky prvky poľa s vybratým otočným prvkom a usporiadajte ich tak, aby prvky menšie ako otočný prvok boli naľavo a väčšie ako otočný prvok na jeho pravej strane.
Nakoniec vykonajte rovnaké operácie s ľavými a pravými bočnými prvkami s otočným prvkom.

To je teda základná osnova rýchleho triedenia. Tu sú kroky, ktoré je potrebné dodržiavať, aby ste mohli vykonať rýchle zoradenie.

Ako funguje QuickSort

Najskôr v poli vyhľadajte prvok „pivot“ .
Začnite ľavým ukazovateľom na prvom prvku poľa.
Začnite pravý ukazovateľ na poslednom prvku poľa.
Porovnajte prvok smerujúci s ľavým ukazovateľom a ak je menší ako otočný prvok, potom posuňte ľavý ukazovateľ doprava (do ľavého indexu pridajte 1). Takto pokračujte, až kým nebude prvok na ľavej strane väčší alebo rovný otočnému prvku.
Porovnajte prvok ukazujúci s pravým ukazovateľom a ak je väčší ako otočný prvok, potom posuňte pravý ukazovateľ doľava (odčítaním 1 od pravého indexu). Pokračujte v tom, kým prvok na pravej strane nie je menší alebo rovnaký ako otočný prvok.
Skontrolujte, či je ľavý ukazovateľ menší alebo rovný pravému ukazovateľu, potom uvidíte elementy v pozíciách týchto ukazovateľov.
Zvýši sa ľavý ukazovateľ a zníži sa pravý ukazovateľ.
Ak je index ľavého ukazovateľa stále menší ako index pravého ukazovateľa, postup opakujte; else vráti index ľavého ukazovateľa.

Pozrime sa teda na tieto kroky s príkladom. Uvažujme pole prvkov, ktoré musíme triediť, je [5,3,7,6,2,9].

Určte prvok Pivot

Predtým, ako začnete s rýchlym triedením, hrá výber prvku otočenia hlavnú úlohu. Ak vyberiete prvý prvok ako otočný prvok, bude mať najhorší výkon v zoradenom poli. Preto je vždy vhodné zvoliť ako otočný prvok stredný prvok (dĺžka poľa vydelený 2) a urobíme to isté.

Tu sú kroky na vykonanie rýchleho triedenia, ktoré sú zobrazené s príkladom [5,3,7,6,2,9].

KROK 1: Určte čap ako stredný prvok. Takže, 7 je otočný prvok.

Krok 2: Začnite ľavý a pravý ukazovateľ ako prvý a posledný prvok poľa. Ľavý ukazovateľ smeruje na 5 pri indexe 0 a pravý ukazovateľ smeruje na 9 pri indexe 5.

KROK 3: Porovnajte prvok na ľavom ukazovateli s otočným prvkom. Pretože 5 <6 posuňte ľavý ukazovateľ doprava na index 1.

KROK 4: Teraz stále 3 <6, takže posuňte ľavý ukazovateľ na jeden ďalší index doprava. Takže teraz 7> 6 zastaví prírastok ľavého ukazovateľa a teraz je ľavý ukazovateľ na indexe 2.

KROK 5: Teraz porovnajte hodnotu v pravom ukazovateli s otočným prvkom. Pretože je 9> 6, posuňte pravý ukazovateľ doľava. Teraz ako 2 <6 zastavte pohyb pravého ukazovateľa.

KROK 6: Zamieňajte obidve hodnoty nachádzajúce sa v ľavom a pravom ukazovateli navzájom.

KROK 7: Posuňte oba ukazovatele o ďalší krok.

KROK 8: Pretože 6 = 6, posuňte ukazovatele na ďalší krok a zastavte sa, keď ľavý ukazovateľ pretína pravý ukazovateľ a vráti index ľavého ukazovateľa.

Takže na základe vyššie uvedeného prístupu musíme napísať kód na výmenu prvkov a rozdelenie poľa, ako je uvedené vo vyššie uvedených krokoch.

Kód na zámenu dvoch čísel v JavaScripte:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Kód na vykonanie oddielu, ako je uvedené vo vyššie uvedených krokoch:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Vykonajte rekurzívnu operáciu

Po vykonaní vyššie uvedených krokov sa vráti index ľavého ukazovateľa a musíme ho použiť na rozdelenie poľa a vykonanie rýchleho triedenia v tejto časti. Preto sa nazýva algoritmus Divide and Conquer.

Rýchle triedenie sa teda vykonáva, kým nie sú zoradené všetky prvky v ľavom a pravom poli.

Poznámka: Rýchle triedenie sa vykonáva na rovnakom poli a v procese sa nevytvárajú žiadne nové polia.

Takže musíme zavolať tento oddiel () vysvetlený vyššie a na základe toho rozdelíme pole na časti. Takže tu je kód, kde ho používate,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Kompletný kód rýchleho triedenia:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]