Sissejuhatus ühendamisse JavaScriptis

Sorteerimise algoritmid on arvutiteaduses väga olulised. Sorteerimise väljund on loendi elementide järjestamine kindlasse järjekorda (kas kasvavalt või kahanevalt). Ühenda sortimine JavaScriptis on üks tõhusamaid sorteerimisalgoritme, kuna see põhineb jagamise ja vallutamise kontseptsioonil. Nagu nimigi ütleb, jagage suurem probleem esmalt väiksemateks probleemideks kui väiksemate probleemide lahendamiseks. Kontseptuaalselt on sorteerimise ühendamine kahe põhilise algoritmi kombinatsioon nimega MERGE ja MERGE_SORT.

mis töötab järgmiselt:

  1. Jagage sortimata loend n arvuks üksikute alamloendite arvuks (n on sortimata loendi elementide koguarv).
  2. Ühendage alamloendid korduvalt sorteeritud alamloenditeks, kuni on ainult üks sorteeritud loend.

Ühendamise sordi rakendamine JavaScriptis

MERGE algoritm järgib kahe sorteeritud loendi ühendamiseks ühte sorteeritud loendisse protseduuri.

Näide: Oletame, et on kaks loendit, st nimekiri 1 (1, 5, 3) ja nimekiri 2 (7, 2, 9).

1. Esmalt sorteerige mõlemad loendid.

Nüüd näeme ja rakendame sellel E-tehnikat.

2. Seejärel loome uue suuruse x + y loendi, kus x on loendi 1 elementide arv ja y on loendi 2 elementide arv.

Meie puhul x = 3 ja y = 3, seega x + y = 6.

3. Nüüd on meil kaks osutust.
Esimene kursor osutab loendi 1 esimesele positsioonile ja teine ​​kursor loendi 2 esimesele positsioonile.

4. Seejärel võrdleme mõlema osuti väärtust. Väiksema väärtusega osuti, kopeerige see element loendisse 3 ja liigutage kursor väiksema väärtuse ja sellest tuleneva loendi (st loend 1 ja loend 3) paremale

5. Samamoodi toimige uuesti 4. ja 4. sammu.

Edasine liikumine …

Märkus . Kui üks loenditest (st 1. või 2. loend) läbitakse täielikult, nagu antud juhul, siis kopeerige kogu muu loendi sisu kursorilt tulemuste loendisse (st 3. loendisse) järgmiselt.

Pseudokood

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)

MERGE_SORT algoritm jagab antud sortimata loendi minimaalseks suuruseks ja kutsub seejärel MERGE algoritmi loendi ühendamiseks uude sorteeritud loendisse.

Pseudokood

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
)

Näide

Jälgime ülalt alla koondamise sortimise rakendamist. See algab ülaosast ja kulgeb allapoole, kusjuures iga rekursiivse pöördega esitatakse sama küsimus “Mida on vaja nimekirja järjestamiseks teha?” Ja vastus on “Jagage loend kaheks, tehke rekursiivne kõne ja ühendage tulemused".

Kood Javascriptis

// 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 )

Ühendamise sorti põhifunktsioon jagab antud loendi väiksemateks loenditeks igas rekursiivse kõne iteratsioonis. Ärge unustage, et lõpmatu rekursiooni vältimiseks on rekursioonil vaja põhitingimust. Meie puhul on meil:

if (list.length < 2) (
return list;// return once we hit a list with a single element
)

Pärast rekursiooni põhitingimuse seadistamist tuvastame keskmise indeksi, et jagada antud loend vasakusse ja paremasse alamloendisse, nagu näete ülaltoodud diagrammil. Seejärel peame ühendama vasaku alamloendi ja parema alamloendi, mida me nüüd vaatame. Ülaltoodud liitmisfunktsioonis peame veenduma, et sorteerime kõik vasakpoolses alamloendis ja paremas alamloendis olevad elemendid. nimekiri. Kuidas me seda teeme, on mõnda aega kasutav silmus. Samal ajal ahelas võrdleme vasakpoolses alamloendis olevat elementi ja paremas alamloendis olevat elementi ükshaaval. Saame lükata kahest väiksema tulemuste loendisse ja vastavalt liigutada vasaku alamloendi ja parema alamloendi kursorit. Lõpuks peame tulemuste loendi siduma. See on väga oluline! Kui me siin seda viimast sammu ei tee, on lõpus elementide loetelu mittetäielik, kuna samas kui silmuse tingimus ebaõnnestub, kui mõni kahest osutist jõuab lõppu.

Väljund:

Ühendamise sordi omadused

  1. Ühendamise sort on stabiilne, kuna massiivi sama element säilitab oma algsed positsioonid üksteise suhtes.
  2. Ühendamise sort pole "paigas", kuna liitmise ajal sorteeritakse kogu loendi koopia. Seetõttu on selle algoritmi ruumi keerukus (O (n)) tegelikult suurem kui teistel ning seda ei tohiks kasutada keerukates probleemides, kus ruum on esmaklassiline.
  3. Ühendamise sorteerimise üldine keerukus on O (nLogn). See on tõhusam, kuna halvimal juhul on ka käitusaeg O (nlogn).

Järeldus

Liitmise sorteerimise parim, halvim ja keskmise juhtumi ajaline keerukus on sama, mis muudab selle algoritmi tõhusamaks. See töötab kiiremini kui muud sorteerimistehnikad. Ühendamise sorteerimist saab rakendada mis tahes suurusega failidele. See on jagamise ja vallutamise meetodi kasutamise tõttu väga paralleelne. Tugevate arvutiteaduse aluste väljatöötamiseks soovitatakse teil põhjalikult mõista erinevaid sortimisalgoritme.

Soovitatav artikkel

See on juhend JavaScripti ühendamise sorteerimiseks. Siin käsitleme sissejuhatust ühendamisse Sorteerimine JavaScriptis ja rakendamine koos atribuutidega. Lisateavet leiate ka meie muudest soovitatud artiklitest -

  1. JavaScripti matemaatikafunktsioonid
  2. Sissejuhatus JavaScripti
  3. Parimad Javascripti raamistikud
  4. JavaScripti tööriistad
  5. Kuus parimat sortimisalgoritmi JavaScriptis

Kategooria:

Tarkvaraarendus