Úvod do zlúčenia zoradenia v JavaScripte
Algoritmy triedenia sú v informatike veľmi dôležité. Výstupom triedenia je usporiadanie prvkov zoznamu do určitého poradia (buď vzostupne alebo zostupne). Zlúčiť triedenie v JavaScripte je jedným z najúčinnejších dostupných algoritmov triedenia, pretože je založený na koncepte rozdelenia a dobývania. Ako už názov napovedá, najprv rozdelte väčší problém na malé problémy, ako vyriešite menšie problémy, aby ste vyriešili väčší problém. Koncepčne je Merge sort kombináciou dvoch základných algoritmov nazývaných MERGE a MERGE_SORT.
ktorý funguje nasledovne:
- Rozdeľte netriedený zoznam do n počtu podzoznamov jednotlivých položiek (n je celkový počet prvkov v netriedenom zozname).
- Opakovane spájajte zoznamy do triedených zoznamov, až kým nebude k dispozícii iba jeden zoznam.
Implementácia zlúčenia zoradenia v JavaScripte
Algoritmus MERGE sa riadi postupom kombinovania dvoch triedených zoznamov do jedného triedeného zoznamu.
Príklad: Predpokladajme, že existujú dva zoznamy, tj zoznam 1 (1, 5, 3) a zoznam 2 (7, 2, 9).
1. Najprv zoraďte oba zoznamy.
Teraz na to uvidíme a použijeme techniku E.
2. Potom vytvoríme nový zoznam veľkostí x + y, kde x je počet prvkov v zozname 1 a y je počet prvkov v zozname 2.
V našom prípade x = 3 a y = 3, takže x + y = 6.
3. Teraz máme dva ukazovatele.
Prvý ukazovateľ smerujúci na prvú pozíciu zoznamu 1 a druhý ukazovateľ ukazujúci na prvú pozíciu zoznamu 2.
4. Potom porovnáme hodnotu oboch ukazovateľov. Ukazovateľ s menšou hodnotou, skopírujte tento prvok do Zoznamu 3 a posuňte ukazovateľ vpravo od zoznamu s menšou hodnotou a výsledným zoznamom (tj Zoznam 1 a Zoznam 3).
5. Podobne opakujte krok 4 znova a znova.
Ďalšie prejdenie … ..
Poznámka : Ak jeden zo zoznamov (tj zoznam 1 alebo zoznam 2) úplne prechádza ako v prípade, skopírujte celý obsah iného zoznamu zo ukazovateľa do zoznamu výsledkov (tj zoznam 3) nasledujúcim spôsobom.
pseudokód
Function merge (sublist1, sublist2) (
Create var for result list
While sublist1 length > 0 and sublist2 length > 0
If sublist1(0) < sublist2(0) Copy the sublist1 pointer value to result list and Shift pointer of sublist1 to right
else
Copy the sublist2 pointer value to result list and Shift pointer of sublist2 to right
Return concat sublist1 or sublist2 (depending if node1 is empty or not)
Algoritmus MERGE_SORT rozdeľuje daný netriedený zoznam na minimálnu veľkosť a potom volá algoritmus MERGE, aby zoznam skombinoval do nového triedeného zoznamu.
pseudokód
function mergeSort(list) (
If list length < 2
Return list
Create var for middle index of list
Create var for left index of list
Create var for right index of list
Recursively call mergeSort function
)
príklad
Tu sledujeme implementáciu zlúčenia zoradenia zhora nadol. Začína sa zhora a pokračuje smerom nadol, pričom pri každom rekurzívnom ťahu sa kladie rovnaká otázka „Čo je potrebné urobiť, aby sa zoznam usporiadal?“ A odpoveďou je „Rozdeliť zoznam na dva, uskutočniť rekurzívny hovor a zlúčiť výsledky ".
Kód v Javascripte
// Split the list into halves and merge them recursively
function mergeSort (list) (
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
var mid = Math.floor(list.length / 2);
var left = mergeSort(list.slice(0, mid));
var right = mergeSort(list.slice(mid));
return merge(left, right);
)
// compare the lists element by element and return the concatenated resultList
function merge (sublist1, sublist2) (
var resultList = ();
while (sublist1.length > 0 && sublist2.length > 0)
resultList.push(sublist1(0) < sublist2(0)? sublist1.shift() : sublist2.shift());
return resultList.concat(sublist1.length? sublist1 : sublist2);
)
const list = (6, 5, 3, 1, 8, 7, 2, 4, 2, 5, 1, 2, 3) console.log(mergeSort(list)) //( 1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 6, 7, 8 )
Hlavnou funkciou zlúčenia je rozdelenie daného zoznamu do menších zoznamov v každej iterácii rekurzívneho hovoru. Nezabudnite, že rekurzia vyžaduje základnú podmienku, aby sa zabránilo nekonečnej rekurzii. V našom prípade máme:
if (list.length < 2) (
return list;// return once we hit a list with a single element
)
Po nastavení základnej podmienky pre rekurziu potom identifikujeme stredný index, ktorý rozdelí daný zoznam na ľavý a pravý pod zoznam, ako vidíte vyššie na príklade. Potom musíme zlúčiť ľavý podadresár a správny podadresár, ktorý teraz uvidíme. Vo vyššie uvedenej funkcii zlúčenia musíme zabezpečiť, aby sme zoradili všetky prvky v ľavom podpriečinku a pravom podpriečinku. zoznam. Budeme to robiť pomocou slučky while. V rámci slučky while budeme porovnávať element v ľavom podzozname a element v pravom podzozname jeden po druhom. Menšie z nich môžeme zatlačiť do zoznamu výsledkov a podľa toho presunúť kurzor v ľavom a pravom podsúbore. Nakoniec musíme zreťaziť zoznam výsledkov. Toto je veľmi dôležité! Ak tu neurobíme tento posledný krok, na konci budeme mať neúplný zoznam prvkov, pretože stav slučky while zlyhá, keď niektorý z dvoch ukazovateľov dosiahne koniec.
Výkon:
Vlastnosti zlúčenia
- Zlúčiť zoradenie je stabilné, pretože ten istý prvok v poli si zachováva svoje pôvodné polohy voči sebe navzájom.
- Zlúčiť zoradenie nie je „na mieste“, pretože pri zlučovaní vytvára kópiu celého zoznamu. Z tohto dôvodu je zložitosť priestoru (O (n)) tohto algoritmu v skutočnosti väčšia ako iné a nemá sa používať v zložitých problémoch, kde je priestor nadštandardný.
- Celková časová zložitosť Merge sort je O (nLogn). Je to efektívnejšie, pretože v najhoršom prípade je runtime O (nlogn).
záver
Zlučovanie najlepších, najhorších a priemerných časových komplikácií zlúčenia je rovnaké, čo z neho robí efektívnejší algoritmus. Funguje to rýchlejšie ako iné techniky triedenia. Zlúčiť zoradenie je možné použiť na súbory ľubovoľnej veľkosti. Je vysoko paralelizovateľný vďaka použitiu metódy rozdelenia a dobytí. S cieľom rozvinúť silné základy počítačovej vedy sa odporúča dôkladne porozumieť rôznym triediacim algoritmom.
Odporúčaný článok
Toto bol sprievodca zlúčením triediť v JavaScripte. Tu diskutujeme Úvod do zlúčenia zoradiť v JavaScripte a implementáciu spolu s Vlastnosti. Viac informácií nájdete aj v ďalších navrhovaných článkoch -
- Matematické funkcie JavaScriptu
- Úvod do JavaScriptu
- Najlepšie Javascriptové rámce
- Nástroje JavaScript
- Top 6 triediaci algoritmus v JavaScripte