Merge Sorter i JavaScript - Ulike typer egenskaper

Introduksjon til Merge Sort i JavaScript

Sorteringsalgoritmer er veldig viktige innen informatikk. Resultatet av sorteringen er å ordne elementene i en liste til en viss rekkefølge (enten stigende eller synkende). Merge Sort in JavaScript er en av de mest effektive sorteringsalgoritmene som er tilgjengelige, fordi den er basert på begrepet skill og erobrere. Som navnet antyder, del først det større problemet i små problemer enn å løse de mindre problemene for å løse det større problemet. Konseptuelt er Merge sort en kombinasjon av to grunnleggende algoritmer kalt MERGE og MERGE_SORT.

som fungerer som følger:

Del den usorterte listen i n antall undelister med ett element (n er det totale antall elementer i den usorterte listen).
Flett sublistene gjentatte ganger til sorterte sublister til det bare er en sortert liste.

Implementering av flettesortering i JavaScript

MERGE-algoritmen følger fremgangsmåten for å kombinere to sorterte lister til en sortert liste.

Eksempel: Anta at det er to lister, dvs. liste 1 (1, 5, 3) og liste 2 (7, 2, 9).

1. Sorter først begge listene.

Nå skal vi se og bruke E-teknikken på den.

2. Deretter vil vi opprette en ny liste med størrelse x + y der x er antall elementer i liste 1 og y er antall elementer i liste 2.

I vårt tilfelle x = 3 og y = 3, så x + y = 6.

3. Nå har vi to tips.
En første peker som peker på den første posisjonen på liste 1 og den andre pekeren som peker på den første posisjonen på liste 2.

4. Så vil vi sammenligne verdien av begge pekere. Pekeren med mindre verdi, kopier det elementet til liste 3 og flytt pekeren til høyre for listen med mindre verdi og den resulterende listen (dvs. liste 1 og liste 3)

5. Utfør trinn 4 igjen og igjen.

Ytterligere å krysse …

Merk : Hvis en av listene (dvs. liste 1 eller liste 2) blir fullstendig krysset som i tilfellet, kopierer du hele innholdet i en annen liste fra pekeren til resultatlisten (dvs. liste 3) som følger.

pseudo

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-algoritmen deler den gitte usorterte listen til minimumsstørrelse og kaller deretter MERGE-algoritmen for å kombinere listen i den nye sorterte listen.

pseudo

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 )

Eksempel

Her følger vi ovenfra og ned Merge Sort implementering. Det starter øverst og fortsetter mot nedover, med hver rekursive sving som stiller det samme spørsmålet "Hva kreves for å gjøre for å sortere listen?" Og har svaret er "Del listen i to, ring en rekursiv samtale og slå sammen resultater”.

Kode i Javascript

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

Hovedfunksjonen for sammenslåingssorteringen vil dele opp den gitte listen i mindre lister i hver iterasjon av den rekursive samtalen. Ikke glem at rekursjon krever basistilstand for å unngå uendelig rekursjon. I vårt tilfelle har vi:

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

Etter at vi har satt opp grunnbetingelsen for rekursjon, identifiserer vi midtindeksen for å dele opp den gitte listen i venstre og høyre underliste, som du kan se ovenfor i eksempelskjemaet. Deretter må vi slå sammen den venstre undelisten og den høyre underlisten som vi vil se ut nå. I flettefunksjonen over, må vi sørge for at vi sorterer alle elementene i venstre undeliste og høyre under- liste. Måten vi gjør dette på er å bruke en stundsløyfe. Innenfor loopen vil vi sammenligne elementet i den venstre underlisten og elementet i den høyre underlisten en etter en. Vi kan skyve den minste av de to inn i resultatlisten og flytte markøren til venstre undeliste og høyre underliste tilsvarende. Til slutt må vi slå sammen resultatlisten. Dette er veldig viktig! Hvis vi ikke gjør dette siste trinnet her, vil vi ha en ufullstendig liste over elementer på slutten fordi tilstandsløyfen vil mislykkes når et av de to pekerne når slutten.

Produksjon:

Egenskaper for flettesortering

Sammenslåingssortering er stabil ettersom det samme elementet i en gruppe opprettholder sine opprinnelige posisjoner i forhold til hverandre.
Sammenslåingssortering er ikke 'på plass', da under sammenslåing skaper det en kopi av hele listen blir sortert. På grunn av dette er romkompleksiteten (O (n)) til denne algoritmen faktisk større enn andre, og ikke til å bli brukt i komplekse problemer der plass er premium.
Den samlede tidskompleksiteten til Merge sort er O (nLogn). Det er mer effektivt, da det i verste fall også er, runtime er O (nlogn).

Konklusjon

Sammenslåing av best mulig, verste og gjennomsnittlige tilfelle av tid er den samme, noe som gjør det til en mer effektiv algoritme. Det fungerer raskere enn andre sorteringsteknikker. Merge sort kan brukes på filer av alle størrelser. Den er svært parallelliserbar på grunn av bruken av skillet og erobre metoden. For å utvikle sterke grunnleggende fag innen informatikk, anbefales du å forstå forskjellige sorteringsalgoritmer grundig.

Anbefalt artikkel

Dette har vært en guide til Merge Sort i JavaScript. Her diskuterer vi Introduksjon til flettesortering i JavaScript og implementeringen sammen med Egenskaper. Du kan også gå gjennom andre foreslåtte artikler for å lære mer -