Innsettingssorter i JavaScript

Innføringssorter er en enkel og stabil sorteringsalgoritme som velger et element fra en usortert liste og setter den inn i den sorterte listen i riktig posisjon. Mens begrepet stabil algoritme refererer til scenariet der to ekvivalente elementer vises identisk, holder en stabil algoritme elementene på sine relative posisjoner etter utførelsen av sorteringsalgoritmen er fullført.

Innsettingssorteringsalgoritme er veldig nyttig i de tilfellene der vi har et mindre antall elementer i en liste eller hvor mesteparten av listen allerede er sortert og færre elementer er feilplassert.

Hvordan innsettingssorter fungerer

La oss vurdere et eksempel for å bedre forstå logikken bak innsettingssorteringen. Anta at vi har et usortert utvalg av 6 elementer, og vi må sortere dem ved hjelp av innsettingssort:

Nå for å sortere ovennevnte matrise, vil vi iterere matrisen fra indeks 1 til siste indeks. Til å begynne med antar vi at den 0. indeksen for matrisen er sortert, deretter vil vi gjøre en sammenligning av det nåværende elementet med dets tidligere element. Hvis det nåværende elementet er mindre enn det tidligere elementet, vil vi bytte posisjoner.

Første skritt
I det første trinnet vil vi sammenligne indeks 1 med indeks 0, verdien av den første indeksen '47' er større enn 0. indeksverdi, så det vil ikke være noen endring i det første trinnet (elementer vil ikke bytte):

Andre trinn
Nå, i det andre trinnet, vil vi anta at de to første elementene er sortert, så markøren vil være på indeks 2, og vi vil sammenligne indeks 2 med dens tidligere elementer:

Siden '25' er mindre enn '47', bytter du '25' og '47'. Neste, '25' sammenlignes også med 0th Index -verdien. '25' er større enn '15', så det ville ikke bli byttet ut.

Arrayen etter det andre trinnet vil bli oppdatert som:

Tredje trinn
Her i det tredje trinnet vurderer vi at de tre første verdiene er sortert og markøren vil være på tredje indeks. Så vi vil sammenligne den tredje indeksen med dens tidligere verdier:

Ved indeks 3, '55' sammenlignes med hvert element ett etter ett, men det er større enn alle tidligere elementer, så det vil ikke være noen endring i posisjonen til matriseelementer.

Fjerde trinn
Nå er vi på indeks 4, der vi har en verdi '20' og vi må sammenligne den med alle tidligere elementer i matrisen:

Siden '20' er mindre enn '25', '47' og '55', så det vil bli satt inn ved første indeks, og '25', '47' og '55' vil bli flyttet til høyre side med en indeks (i+1 indeks) fra gjeldende indekser.

Den oppdaterte matrisen vil være:

Femte trinn
Nå er vi på indeks 5 der gjeldende verdi er '10', som er den minste blant alle matriseverdiene, så den vil bli satt inn i 0. indeksen.

På denne måten vil hele matrisen bli sortert ved hjelp av innsettingssorter:

Når vi er ferdige med den konseptuelle delen av innsettingssorter, vil vi nå implementere dette konseptet i JavaScript.

Implementering av innsettingssorter i JavaScript

Koden for implementering av innsettingssorter i JavaScript er som følger:

funksjon Insertion_sort (input_array, array_length)

la jeg, pivot_value, j;
for (i = 1; i = 0 && input_array [j]> pivot_value)

input_array [j + 1] = input_array [j];
j = j - 1;

input_array [j + 1] = pivot_value;

return input_array;

La input_array = [15,47,25,55,20,10];
la array_length = input_array.lengde;
insertion_sort (input_array, array_length);
konsoll.Logg ("endelig sortert matrise:", input_array);

I koden ovenfor opprettet vi en funksjon "innsetting_sort”Og passerte den inngangsarrayen og array -lengden. Så itererte vi sløyfen til lengden på matrisen.

Inne i sløyfen valgte vi 'pivot_value = input_array [i]'Som en svingverdi for å gjøre en sammenligning av det nåværende elementet med dets tidligere elementer og sett "j = i-1”Som representerer det siste elementet i vårt sorterte matrise.

Her i hver iterasjon blir det nåværende elementet tilordnet pivotverdien, og pivotverdien vil bli betraktet som det første elementet i den usorterte matrisen i hvert trinn.

Vi bruker en stundsløyfe for å sortere matriseelementer, her i denne sløyfen sammenligner vi det nåværende elementet med dets tidligere elementer. Hvis det nåværende elementet er mindre enn noen av de tidligere elementene, og vi fant passende posisjon til å sette inn dette elementet i det sorterte matrisen, setter vi inn dette elementet i riktig posisjon og flytter de andre elementene ett sted til høyre side. Og hele fenomenet gjentas for hvert trinn til matrisen er sortert fullstendig.

Produksjon

Endelig kaller vi "innsetting_sort”Funksjon og skriv ut den sorterte matrisen på konsollen til nettleseren ved å bruke“konsoll.Logg”Metode. Utgangen fra innsettingssortalgoritmen vil være:

Konklusjon

Innføringssorter er en sorteringsalgoritme som sorterer ett element om gangen. Den setter inn elementet i passende posisjon en etter en for å lage en sortert matrise. Det gir effektive resultater hvis antallet matriseelementer er lite og de fleste av matriseelementene allerede er sortert.

I denne artikkelen vurderte vi et eksempel for å finne ut logikken i innsettingssort, vi diskuterte arbeidet med innsettingssortalgoritmen med hensyn til hvert trinn og presenterer den oppdaterte matrisen etter hvert trinn. Og til slutt, når vi oppfattet ideen bak innsettingssorteringen, implementerte vi den i JavaScript.