Rask sorter i JavaScript

Quicksort-algoritmen deler listen inn i underliste, kombinerer deretter disse underlistene for å oppnå en sortert liste. Den bruker skillet og erobrer tilnærmingen for å sortere matrens elementer. Det er mange algoritmer tilgjengelig for å sortere en liste, men Quicksort regnes som en av de beste blant alle disse algoritmene.

Hvor rask sorteringsalgoritme fungerer

Quicksort -algoritmen plukker et element og anser det som et pivotelement; Nå er svingelementet reservert.

Deretter tar vi de to pekerne 'P' og 'Q'.

'P' pekeren vil bevege seg fra venstre side til høyre side, og den vil ikke stoppe før den finner et større enn eller lik pivotelementet.

Den andre pekeren 'Q' vil bevege seg fra høyre side til venstre, og den vil slutte å søke når den finner et element mindre enn eller lik pivotelementet.

Så 'P' vil sortere de mindre elementene på venstre side og 'Q' vil sortere de større elementene på høyre side.

Nå skal vi forstå arbeidet med Quick Sort -algoritmen ved hjelp av et eksempel:

Anta at vi har en rekke seks elementer, og vi vil sortere den i stigende rekkefølge ved hjelp av en QuickSort -algoritme:

I det første trinnet velger vi '36' som et pivotelement (midtelement):

I neste trinn velger vi våre pekere, 'P' peker for å gå fra venstre til høyre og 'q' peker for å bevege seg fra høyre side til venstre side:

Nå vil verdien av venstre peker 'P' sammenlignes med pivotverdien, ettersom '35' er mindre enn '36' flytt 'P' pekeren til det tilstøtende elementet. På den annen side kan du sammenligne verdien av riktig peker 'Q' med pivotverdien, '39' er større enn '36', så 'Q' -pekeren vil bevege seg til det venstre tilstøtende elementet:

Nå peker 'P' -pekeren på '33' og blir sammenlignet med Pivot '36', verdien av pekeren 'P' er mindre enn pivotverdien, derfor vil pekeren 'p' bli flyttet til det tilstøtende elementet. Mens 'Q' pekerens verdi '32' er mindre enn svingverdien '36', så vil den stoppe her:

Venstre pekerens verdi '37' er større enn Pivots verdi '36', så den vil også stoppe her. Nå stopper 'P' på '37' og 'Q' på '32'.

Nå vil vi sjekke om 'P' pekeren krysser 'Q' -pekeren eller ikke. I dette tilfellet krysser ikke P 'hittil ikke' Q '-pekeren, så vi vil bytte verdien av pekeren' P 'med verdien av pekeren' Q ':

Nå skifter 'P' og 'Q' på henholdsvis '32' og '37', skifter pekerne en gang til, nå p = q ('36 '=' 36 '):

Flytt pekerne en gang til, da 'P' -pekeren krysser 'Q' -pekeren, så her, vil den stoppe og returnere indeksen til 'P' pekeren. Frem til nå er pivotelementet i sin rette posisjon og alle elementene som er større enn pivotelementet er på høyre side av pivoten, og alle elementene mindre enn pivotelementer er på venstre side av pivot. På denne måten vil vi sortere hele listen.

Nå vil vi implementere dette konseptet i JavaScript. Først koden for å bytte elementer:

funksjon Swap_elements (elementer, venstre_index, høyre_inde)
var temp = elementer [venstre_index];
elementer [venstre_index] = elementer [høyre_index];
elementer [høyre_index] = temp;

Deretter koden for å dele en liste i underlister:

funksjon sub_lister (elementer, venstre_punkt, høyre_punkt)
var pivot = elementer [matematikk.gulv ((høyre_pointer + venstre_pointer) / 2)],
i = venstre_pointer,
j = høyre_punkt;
mens jeg <= j)
mens (elementer [i] pivot)
j--;

if (i 1)
indeks = sub_lister (elementer, venstre_punkt, høyre_punkt);
if (venstre_pointer < index - 1)
Quick_sort (elementer, venstre_punkt, indeks - 1);

hvis (indeks < right_pointer)
QUICK_SORT (elementer, indeks, right_pointer);


returelementer;

Vi opprettet en funksjon som tar tre parametere i funksjonen. Vi deler hele listen i underlister og finner ut venstre peker og høyre peker, og vi skriver koden for å øke venstre peker hvis den er mindre enn svingelementet og reduserer høyre peker hvis den er større enn pivotelementet:

Nå skal vi skrive koden for å håndtere den rekursive oppførselen til den raske sorteringen. Siden i ovennevnte trinn blir venstre_punkts indeks returnert, og vi vil bruke den til å dele opp listen i underlister og for å bruke Quicksort på disse underlistene:

funksjon QUICK_SORT (Elements, Left_Pointer, Right_Pointer)
var indeks;
hvis (elementer.lengde> 1)
indeks = sub_lister (elementer, venstre_punkt, høyre_punkt);
if (venstre_pointer < index - 1)
Quick_sort (elementer, venstre_punkt, indeks - 1);

hvis (indeks < right_pointer)
QUICK_SORT (elementer, indeks, right_pointer);


returelementer;

Det komplette kodebiten vil gå slik:

var elementer = [35,33,37,36,32,39];
funksjon Swap_elements (elementer, venstre_index, høyre_inde)
var temp = elementer [venstre_index];
elementer [venstre_index] = elementer [høyre_index];
elementer [høyre_index] = temp;

funksjon sub_lister (elementer, venstre_punkt, høyre_punkt)
var pivot = elementer [matematikk.gulv ((høyre_pointer + venstre_pointer) / 2)],
i = venstre_pointer,
j = høyre_punkt;
mens jeg <= j)
mens (elementer [i] pivot)
j--;

if (i 1)
indeks = sub_lister (elementer, venstre_punkt, høyre_punkt);
if (venstre_pointer < index - 1)
Quick_sort (elementer, venstre_punkt, indeks - 1);

hvis (indeks < right_pointer)
QUICK_SORT (elementer, indeks, right_pointer);


returelementer;

var sorted_array = quick_sort (elementer, 0, elementer.lengde - 1);
konsoll.logg ("den sorterte listen:", sortert_array);

Vi initialiserte den usorterte matrisen ved starten av programmet, og på slutten av programmet kalte vi "Quick_sort ()" -funksjonen for å få den endelige sorterte matrisen:

Til slutt, når vi kjører denne koden, får vi den resulterende utgangen som:

Konklusjon:

Quicksort er en sorteringsalgoritme som fungerer på skillet og erobrer filosofi og deler problemet i mindre underproblemer. Og fortsett denne prosessen til du oppnår det resulterende målet. I denne artikkelen diskuterer vi hvordan Quicksort fungerer og implementerer dette konseptet i JavaScript for å ordne opp for enhver matrise på den mest effektive måten.