Valgssorter i JavaScript

Valgssorteringsalgoritmen sorterer listen ved å finne det minste nummeret fra den usorterte listen og flytte den til begynnelsen av listen. Valgssort deler den faktiske listen i to lister, en for sorterte tall mens den andre listen er for de gjenværende usorterte tallene, i utgangspunktet anser den hele listen som en usortert liste.

Valgssort fungerer på en veldig grunnleggende filosofi som skal finne det minste tallet i matrisen og bytte den til startposisjonen (0. indeks), og finn igjen det nest minste tallet fra den gjenværende usorterte matrisen og plasser den til riktig posisjon ( første indeks) og så videre, på denne måten endelig, vil vi få en sortert matrise.

I denne artikkelen vil vi diskutere hvordan utvalgssort fungerer, for dette formålet vil vi vurdere et eksempel for å forklare hvert trinn for å sortere en matrise ved hjelp av valgsort.

Hvordan utvalgssorter fungerer

Tenk for eksempel følgende matrise og sorter den ved hjelp av Selection Sort:

Trinn 1

Til å begynne med har vi en rekke fem elementer, ved indeks null har vi en verdi '9', og vi vil sammenligne den med neste indeks, hvis verdien av den første indeksen er mindre enn verdien av null-indeks, så neste gang vi vil sammenligne verdien av indeks 1 med de gjenværende matriseelementene.

Vi sammenligner '1' med '8', '1' er mindre enn '8', så igjen vil vi sammenligne '1' med verdien av neste indeks (3. indeks),

'1' er mindre enn '2'.

Det betyr igjen '1' vil bli sammenlignet med den siste indeksen der vi fant en verdi '4' som også er større enn '1'.

Så trinn for trinn sammenligner vi 1 med hvert element i matrisen, og som et resultat var vi vitne til at '1' er det minste antallet blant alle matriseelementene.

Så endelig fikk vi en sortert verdi for indeksen 0.

Steg 2:

Nå etter trinn 1 er verdien ved indeks null sortert, så vi har to seksjoner nå, på venstre side en sortert matrise og på høyre side en usortert matrise:

Vi vil sortere det usorterte matrisen, så i utgangspunktet vil vi sammenligne indeks en med indeks to, vi fant at '9' er større enn '8'

Ettersom '8' er mindre enn '9', så herfra vil vi sammenligne verdien av indeks 2 som er '8' med de andre arrayelementene. Nå blir '8' sammenlignet med '2'

'2' er mindre enn '8' Derfor vil vi i neste iterasjon sammenligne '2' med de siste arrayelementene. Sammenlign '2' med '4':

Så '2' er det minste elementet blant alle de usorterte matriseelementene, så vil bli byttet ved den andre indeksen, resulterende matrise etter det andre trinnet vil være:

Trinn 3

Så langt har vi sortert 2 elementer, mens tre elementer er usortert. Nå vil vi sortere de gjenværende usorterte elementene i matrisen. For dette formålet, sammenlign verdien av indeks 2 med verdien av indeks 3, så det vil ikke være noen endring da '8' er mindre enn '9'. I neste iterasjon sammenligner vi '8' med verdien av den endelige indeksen.

Her er '4' mindre enn '8' og '4' er det siste elementet i matrisen, derfor vil '4' bli byttet med '8': og den oppdaterte matrisen vil være:

Trinn 4:

Nå er de tre første elementene sortert, sammenligner verdien av indeks 3 med verdien av indeks 4, her er '9' større enn '8' og det er ikke mer element igjen i matrisen for sammenligningen, derfor byttet vi Verdien av Forth -indeks med verdien av den tredje indeksen:

Til slutt får vi et sortert utvalg, dessuten, hvis noen blir bedt om å sortere i synkende rekkefølge, vil det bli gjort i omvendt rekkefølge ved å finne maksimal verdi.

Hvordan implementere valgsort i JavaScript

Nå vil vi konkludere med å arbeide med valg av sort i forhold til hvert trinn, og da vil vi implementere det samme konseptet i JavaScript.

Etter å ha fullført det første trinnet, får vi minimumsverdien ved 0th -indeksen, i det andre trinnet blir det nest minste tallet flyttet til den første indeksen. Tilsvarende får vi et riktig antall på riktig indeks etter å ha fullført det tredje og fjerde trinnet.

Vi trenger ikke å utføre sortering for den siste indeksen, da vi bare har ett element igjen, og hvis alle tidligere elementer i matrisen er sortert, vil det siste elementet også bli sortert.

Derfor konkluderte vi med at vi krever totalt “N-1” trinn for å sortere en matrise.

Nå vil vi implementere dette utvalgskonseptet i JavaScript:

funksjonsvalg_sort (input_array)
la array_length = input_array.lengde;
for (la i = 0; iLa minste = i;
for (la j = i+1; j if (input_array [j] minste = j;


hvis (minste != i)
la temp_val = input_array [i];
input_array [i] = input_array [minste];
input_array [minste] = temp_val;


return input_array;

const input_array = [9, 1, 8, 2, 4];
utvalg_sort (input_array);
konsoll.Logg ("endelig sortert matrise:", input_array);

I den første delen av koden bruker vi “.lengde" Eiendom for å sjekke lengden på selve matrisen og lagre den i en variabel “array_length”, så itererer vi løkken til den når "n-1" -indeksen. I løkka opprinnelig vurderer vi at den gjeldende indeksen har den minste verdien, derfor setter vi "minste = i" og neste gang bruker vi en annen for-loop for å sammenligne den nåværende verdien med de gjenværende verdiene til matrisen, og sløyfen vil Start fra “I+1”. Deretter skriver vi koden for å bytte elementet når vi har funnet det minste elementet i matrisen.

Endelig benyttet vi konsoll.Logg() Funksjon til utdataene på nettleserens konsoll:

Konklusjon

I utvalgssorteringsalgoritmen finner vi det minste elementet. Vi flytter den til den første indeksen, og flytter deretter det nest minst elementet til den første indeksen, og så videre. Som et resultat får vi en rekke der de sorterte elementene er til stede på venstre side og de usorterte elementene er til stede på høyre side av matrisen. På denne måten er en endelig sortert matrise konstruert ved hjelp av Selection Sort i JavaScript.

I denne artikkelen har vi lært hvordan du sorterer en matrise ved hjelp av Selection Sort i JavaScript. Vi forstår logikken bak utvalgssorteringsalgoritmen ved å vurdere et eksempel og forklare dens fungerende trinn for trinn.