QuickSort-algoritme i JavaScript

Hva er Quick Sort?

Quick Sort algoritme følger Divide and Conquer tilnærming. Den deler elementer i mindre deler basert på noen tilstand og utfører sorteringsoperasjoner på de delte mindre delene.

Rask sorteringsalgoritme er en av de mest brukte og populære algoritmene i ethvert programmeringsspråk. Men hvis du er JavaScript-utvikler, kan du høre om sort () som allerede er tilgjengelig i JavaScript. Da har du kanskje tenkt på hva behovet til denne Quick Sort-algoritmen er. For å forstå dette trenger vi først hva som er sortering og hva som er standard sortering i JavaScript.

Hva er sortering?

Sortering er ikke annet enn å ordne elementer i den rekkefølgen vi ønsker. Du har kanskje kommet over dette på skoledagen eller på college-dagen. Som å ordne tall fra mindre til større (stigende) eller fra større til mindre (synkende) er det vi så til nå og kalles sortering.

Standard sortering i JavaScript

Som nevnt tidligere har JavaScript sortert () . La oss ta et eksempel med få matriser av elementer som [5,3,7,6,2,9] og ønsker å sortere disse matriseelementene i stigende rekkefølge. Bare ring sort () på elementarray, og den sorterer arrayelementer i stigende rekkefølge.

Kode:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

Hva er grunnen til å velge Hurtig sortering over standardsortering () i JavaScript

Selv om sort () gir det resultatet vi ønsker, ligger problemet i måten det sorterer matriseelementene. Standardsortering () i JavaScript bruker innsettingssortering etter V8 Engine i Chrome og Flett sortering etter Mozilla Firefox og Safari .

Men annet er dette ikke egnet hvis du trenger å sortere et stort antall elementer. Så løsningen er å bruke hurtig sortering for store datasett.

Så for å forstå det helt, må du vite hvordan Quick sort fungerer, og la oss se det i detalj nå.

Hva er Quick sort?

Rask sortering følger Divide and Conquer algoritme. Det deler elementene inn i mindre deler basert på noen tilstand og utfører sorteringsoperasjoner på de delte mindre delene. Derfor fungerer det bra for store datasett. Så her er trinnene hvordan rask sortering fungerer i enkle ord.

Velg først et element som skal kalles som pivotelement .
Deretter sammenligner du alle matriseelementer med det valgte pivotelementet og ordner dem på en slik måte at elementer mindre enn pivotelementet er til venstre og større enn pivot er til høyre.
Til slutt, utfør de samme operasjonene på venstre og høyre sideelement til pivotelementet.

Så det er den grunnleggende oversikten over Rask sortering. Her er trinnene som må følges en etter en for å utføre rask sortering.

Hvordan fungerer QuickSort

Finn først "pivot" -elementet i matrisen.
Start venstre peker ved første element i matrisen.
Start høyre peker på det siste elementet i matrisen.
Sammenlign elementet som peker med venstre peker, og hvis det er mindre enn pivotelementet, flytt deretter venstre peker til høyre (legg 1 til venstre indeks). Fortsett dette til venstre sideelement er større enn eller lik dreieelementet.
Sammenlign elementet som peker med høyre peker, og hvis det er større enn pivotelementet, flytt deretter høyre peker til venstre (trekk 1 til høyre indeks). Fortsett dette til høyre sideelement er mindre enn eller lik dreieelementet.
Sjekk om venstre peker er mindre enn eller lik høyre peker, så så elementene på plassering av disse pekerne.
Øk venstre peker og reduser høyre peker.
Hvis indeksen til venstre peker fortsatt er mindre enn indeksen til høyre peker, gjenta prosessen. Ellers returnerer du indeksen til venstre peker.

Så, la oss se disse trinnene med et eksempel. La oss vurdere en rekke elementer som vi trenger å sortere er [5,3,7,6,2,9].

Bestem dreieelement

Men før du går videre med hurtig sortering, spiller valg av pivot-element en viktig rolle. Hvis du velger det første elementet som pivotelementet, gir det dårligst ytelse i den sorterte matrisen. Så det anbefales alltid å velge midtelementet (lengden på matrisen delt på 2) som dreieelementet, og vi gjør det samme.

Her er trinnene for å utføre rask sortering som vises med et eksempel [5,3,7,6,2,9].

TRINN 1: Bestem sving som midtelement. Så 7 er hovedelementet.

TRINN 2: Start venstre og høyre pekepinner som henholdsvis første og siste element i matrisen. Så, venstre peker peker på 5 ved indeks 0 og høyre peker på 9 på indeks 5.

TRINN 3: Sammenlign element til venstre pekeren med dreieelementet. Siden, skift 5 <6 venstre peker til høyre for indeks 1.

TRINN 4: Nå, fortsatt 3 <6, så skift venstre peker til en indeks til høyre. Så nå slutter 7> 6 å øke den venstre pekeren, og nå er den venstre pekeren på indeks 2.

TRINN 5: Sammenlign nå verdien til høyre peker med dreieelementet. Siden 9> 6 flytter du høyre peker mot venstre. Nå som 2 <6 slutter å flytte høyre peker.

TRINN 6: Bytt begge verdiene til venstre og høyre pekere med hverandre.

TRINN 7: Flytt begge pekerne ett trinn til.

TRINN 8: Siden 6 = 6, flytt pekepinnene til ett trinn og stopp når venstre peker krysser høyre peker og returnerer indeksen til venstre peker.

Så her, basert på ovennevnte tilnærming, trenger vi å skrive kode for å bytte elementer og partisjonere matrisen som nevnt i trinnene ovenfor.

Kode for å bytte to tall i JavaScript:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Kode for å utføre partisjonen som nevnt i trinnene ovenfor:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Utfør den rekursive operasjonen

Når du har utført trinnene ovenfor, vil indeksen til venstre peker bli returnert, og vi må bruke den til å dele opp matrisen og utføre hurtig sortering på den delen. Derfor kalles det Divide and Conquer algoritme.

Så, Rask sortering utføres til alle elementene i venstre array og høyre array er sortert.

Merk: Rask sortering utføres på samme matrise, og ingen nye matriser opprettes i prosessen.

Så vi må kalle denne partisjonen () forklart ovenfor og basert på at vi deler opp matrisen i deler. Så her er koden der du bruker den,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Komplett rask sorteringskode:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]