Úvod do rýchleho triedenia v JavaScripte
Algoritmus triedenia je jednou z dôležitých častí štruktúry údajov. Triedenie je spôsob usporiadania skupiny položiek určeným spôsobom. Kedykoľvek diskutujeme o rýchlejšom triediacom algoritme, prichádza do hry Quick Sort. Toto je jedna z najpopulárnejších metód triedenia podľa času vykonávania. Je to porovnateľne lepšia voľba akéhokoľvek vývojára alebo kódovača kvôli jeho výkonu. Rýchle zoradenie funguje na základe pravidla rozdelenia a dobývania. To znamená, že rozdeľuje zoznam na dva a potom dva zoznamy ďalej rozdelené do 4 rekurzívne a tak ďalej. V tomto článku sa dozvieme, ako rýchle zoradenie funguje aj s príkladom kódu. Uvidíme tiež, že je rýchlejší v porovnaní s inými rôznymi triediacimi algoritmami. Uvidíme rôzne zložky tohto algoritmu rýchleho zoradenia.
Operácie v rýchlom triedení
V rýchlom triedení JavaScript existujú tri hlavné operácie:
- Rozdelenie zoznamu: Delenie alebo zoznam polí pomocou delenia a dobývania. Toto je prvý krok, ktorý môžeme v tejto triediacej technike povedať. Preto potrebujeme Otočný prvok (stredný prvok alebo blízko stredného prvku).
- Výmena položiek: Toto je hlavným účelom akéhokoľvek algoritmu triedenia, ktorý by sa dostal na zoznam želaní ako výstup. Toto je mechanizmus na zoradenie nahradenia hodnoty z jedného na druhý. Napríklad A = 10; B = 20; Ak niekto požiada o výmenu, hodnota A bude 20 a B bude 10.
- Rekurzívna prevádzka: Toto hrá veľkú úlohu pri rýchlom triedení. Ako robiť veci znova a znova, nie je to také možné a spoľahlivé bez toho, aby mali rekurzívnu funkciu. Je to niečo, čo funkcia sama osebe nazýva (rovnaká funkcia), aby sa práca dokončila. To hrá veľkú úlohu, keď vykonávame každú úlohu znova a znova s rovnakým prístupom av rovnakom kontexte.
Porovnanie triediaceho algoritmu
Existuje celý rad algoritmov triedenia. Pretože JavaScript je programovací jazyk, podporuje všetky triediace algoritmy. Každý triediaci algoritmus má svoje klady a zápory. Tu je zoznam triediacich algoritmov a ich výkonu a ďalších matíc:
| Algoritmus triedenia | Časová zložitosť | ||
| Najlepší prípad | Priemerný prípad | V najhoršom prípade | |
| Triedenie bubliniek | Ω (N) | Θ (N 2 ) | O (N 2 ) |
| Výber Zoradiť | Ω (N 2 ) | Θ (N 2 ) | O (N 2 ) |
| Zoradenie vloženia | Ω (N) | Θ (N 2 ) | O (N 2 ) |
| Zlúčiť zoradenie | Ω (N log N) | Θ (N log N) | O (N log N) |
| Usporiadanie haldy | Ω (N log N) | Θ (N log N) | O (N log N) |
| Rýchle zoradenie | Ω (N log N) | Θ (N log N) | O (N 2 ) |
Ako vidíme v zozname, RÝCHLE triedenie je rýchlejšie ako triedenie bubliniek, triedenie výberu, triedenie vloženia.
Ako funguje rýchle zoradenie v jazyku JavaScript?
Krok 1 : Získanie prvku Pivot - Pri každom rozdelení a dobytí hrá dôležitú úlohu výber správneho pivotu. Spravidla sa teda snažíme získať stredný prvok poľa ako prvok Pivot. Toto je prvok, z ktorého rozdelíme jednotlivé pole na pokoj dvoch, aby sme mohli triedenie spracovať.
Krok 2 : Spustite ľavé ukazovatele ako prvý prvok vstupného poľa.
Krok 3 : Spustite pravé ukazovatele ako posledný prvok vstupného poľa.
Krok 4 : Teraz porovnávame prvky na ľavom ukazovateli s vybraným prvkom pivotu a hodnotu podľa potreby vymieňame podľa obchodných požiadaviek. Potom porovnávame pravý ukazovateľ s prvkom Pivot.
Krok 5: Presuňte obe na ďalšiu. Všetky vyššie uvedené kroky nasledujú znova a znova pomocou rekurzívneho prístupu.
Príklad rýchleho zoradenia v JavaScripte
Toto je funkcia, ktorá sa postará o rýchle zoradenie v JavaScripte. V tomto odovzdáme kompletný zoznam poľa ako vstup a dostaneme zoradené pole ako výstup.
Quick Sort in JavaScript
function quick_Sorting(array) (
if (array.length <= 1) (
return array; // if there is only one element then return the same
) else
(
var left = ();
var right = ();
var outputArray = ();
var pivot = array.pop();
var length = array.length;
for (var i = 0; i < length; i++) (
if (array(i) <= pivot) (
left.push(array(i));
) else (
right.push(array(i));
)
)
return outputArray.concat(quick_Sorting(left), pivot, quick_Sorting(right));
)
)
var myList = (3, 10, 2, 5, -5, 4, 7, 1);
alert("Input Array List: " + myList);
var sortedList = quick_Sorting(myList);
alert("Output Array List: " + sortedList);
Vďaka svojmu úžasnému výkonu používa väčšina kodéra túto techniku triedenia na implementáciu zabudovanej funkcie triedenia. V rôznych programovacích jazykoch sa používa rýchle triedenie pre zabudovanú funkciu triedenia. Existujú rôzne iné spôsoby, ako napísať program na vykonanie operácií rýchleho zoradenia a všetky funkcie sa stretnú do bodu Rozdeľ a Doby. Toto rozdelenie a dobitie je teda pravidlo narážania, ktoré sa spracuje pomocou rýchleho zoradenia v JavaScripte. Nielen v JavaScripte, ale aj vo všetkých programovacích jazykoch.
Výkon:
Odporúčané články
Toto je sprievodca rýchlym triedením v JavaScripte. Tu diskutujeme o tom, ako rýchle triedenie funguje v javascripte, o jeho operáciách a o porovnaní triediaceho algoritmu spolu s príkladom. Ďalšie informácie nájdete aj v nasledujúcich článkoch -
- Príklady implementácie rýchleho zoradenia v jazyku Java
- Čo je to Prípad v jazyku JavaScript?
- Vlastnosti zlúčenia zoradiť v JavaScripte
- Typy konštruktorov v JavaScripte
- Halda Zoradiť v Pythone
- Výmena v PHP
- Vloženie Zoradiť v JavaScripte
- Rekurzívna funkcia v C
- Rekurzívna funkcia v JavaScripte