Slå sammen i JavaScript

Fusjonsortering deler den komplette listen inn i sublister eller i “n” sublister, og den fortsetter denne prosessen rekursivt til hver underliste har ett element. Når denne "Divide and Conquer" -prosessen er fullført, begynner den å slå sammen hver underliste for å lage en sortert liste.

Hvordan Merge Sort fungerer

Nå skal vi forstå arbeidet med fusjonssort ved hjelp av et eksempel:

La oss vurdere et annet eksempel for Merge Sort der vi har totalt syv (rare) elementer i en matrise, og vi vil sortere dem i stigende rekkefølge:

[5, 7, 1, 4, 6, 3, 2]

Del matrisen i to underarriser

[5, 7, 1] og [4, 6, 3, 2]

Igjen vil hver matrise bli delt inn i to subarrays

[5], [7, 1] og [4, 6], [3, 2]

Her av fire undergarriser har den ene undergruppen bare ett element, men de tre andre matriser har fremdeles mer enn ett element, så vi vil dele hver av disse matriser ytterligere i to matriser.

[5], [7], [1], [4], [6], [3], [2]

Nå er det første trinnet komplett, da hver matrise bare har ett element i det. Nå vil vi sammenligne matriseelementene og slå sammen disse enkeltvare -matriser i par.

[5, 7], [1, 4], [3, 6], [2]

Vi gjør en sammenligning mellom matriseelementene i de to første matriser og de to siste matriser og flytter de mindre verdiene til venstre side og større verdier til høyre side.

En sammenligning mellom elementene i de to første matriser og de to andre matriser vil bli gjennomført. For eksempel er de to første matriser [5,7] og [1,4]. 5 vil for det første bli sammenlignet med 1 og deretter til 4. Etterpå vil det andre elementet som er 7 gjennomgå samme prosedyre, og den resulterende matrisen vil være [1,4,5,7]. Nå vil vi håndtere de to siste matriser som er [3,6] og [2]. Etter sammenligning vil matrisen vi får være [2,3,6].

[1, 4, 5, 7] [2, 3, 6]

Nå har vi to matriser; [1,4,5,7] og [2,3,6]. La oss ringe dem Arraya [1,4,5,7] og Arrayb [2,3,6] henholdsvis.

Først av alt, det første elementet “1”Av Arraya vil bli sammenlignet med det andre elementet “2”Av Arrayb og det mindre antallet “1”Vil bli lagret i den nye sorterte matrisen

[1]

I neste iterasjon, "2”Vil bli sammenlignet med neste element”4”Av Arraya. Den mindre “2”Vil bli lagret i den nye sorterte matrisen.

[1,2]

Denne gangen vil “4” av Arraya bli sammenlignet med neste element “3” av Arrayb. Ettersom “3” er mindre, så den blir satt inn i den nye sorterte matrisen.

[1,2,3]

Denne prosedyren vil bli gjort med hvert element av begge matriser, og når alle elementer er sammenlignet, vil den resulterende matrisen være; [1,2,3,4,5,6,7].

[1, 2, 3, 4, 5, 6, 7]

Slå sammen i JavaScript

Som vi har lært hvordan Merge Sort fungerer nå, vil vi kode det i JavaScript.

Lag en rekursiv funksjon for å dele den usorterte matrisen, vi kalte den “Merge_sort”. Den rekursive funksjonen har alltid en basesak for å stoppe programmet. Vi gir den usorterte matrisen til “Merge_sort”Funksjon, og inne i denne funksjonen finner vi midtindeksen til matrisen ved å dele opp matrisens lengde med 2. Videre bruker vi metoden “Splice ()” for å dele opp matrisen i undergarrayer.

funksjon Merge_sort (unsortedArray)
const Midle_index = UsortertArray.lengde / 2
hvis (usortert om.lengde < 2)
Returner UsortedArray

Const LeftArray = UsortertArray.Splice (0, Midle_index)
Return MergeArray (Merge_Sort (LeftArray), Merge_Sort (UsortertArray))

Nå vil vi diskutere koden for å slå sammen de to splittende matriser. Disse splittende matriser er allerede sortert i "Merge_sort" -funksjonen, og nå slår vi sammen dem i "Mergaarrays”Funksjon.

Funksjon Mergaarrays (venstreorray, RightArray)
La ary = []
mens (venstre.Lengde && RightArray.lengde)
if (leftarray [0] < rightArray[0])
ary.Push (LeftArray.skifte())
annet
ary.Push (RightArray.skifte())


Returner [… Ary,… LeftArray,… RightArray]

I den ovennevnte funksjonen "LeftArray" og "RightArray" er de to sorterte matriser, og vi slår dem sammen for å få en enkelt sortert matrise. To metoder brukes i dette eksemplet: “trykk()”Metode for å legge til verdien på slutten av den sorterte matrisen og“skifte()”Metode for å slette verdien som er valgt fra underarray. Til slutt, konsollen.Log () -metoden brukes til å teste utgangen.

Det komplette kodebiten vil gå slik:

Funksjon Mergaarrays (venstreorray, RightArray)
La ary = []
mens (venstre.Lengde && RightArray.lengde)
if (leftarray [0] < rightArray[0])
ary.Push (LeftArray.skifte())
annet
ary.Push (RightArray.skifte())


Returner [… Ary,… LeftArray,… RightArray]

funksjon Merge_sort (unsortedArray)
const Midle_index = UsortertArray.lengde / 2
hvis (usortert om.lengde < 2)
Returner UsortedArray

Const LeftArray = UsortertArray.Splice (0, Midle_index)
Return MergeArrays (Merge_Sort (LeftArray), Merge_Sort (UsortertArray))

usortertArray = [5, 7, 1, 4, 6, 3, 2];
konsoll.Logg (Merge_sort (UNSORTEDEDARRAY));

Produksjon:

Konklusjon:

Slå sammen deler deler en liste i underlister, og den fortsetter å dele listen til en underliste får et enkelt element, så smelter den sammen alle underlistene og produserer en ny sortert liste. I dette innlegget lærte vi begrepet Merge Sort, så vurderte vi noen eksempler, og til slutt implementerte vi dem i JavaScript. Vi har også forklart hvordan skjøtemetoden, push -metoden og skiftmetoden fungerer i JavaScript.