QuickSort Algoritme inn JavaScript

Hva er sortering?

Sortering er ikke annet enn å ordne elementer i den rekkefølgen vi ønsker. Du kan ha kommet over dette i skole- eller høyskoletiden. 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 JavaScript

Som nevnt tidligere, JavaScript har sortere(). La oss ta et eksempel med få array av elementer som [5,3,7,6,2,9] og ønsker å sortere disse array-elementene i stigende rekkefølge. Bare ring sortere() på elementer array og den sorterer array-elementer 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 Quick sort over standard sort() in JavaScript

Selv om sort() gir resultatet vi ønsker, ligger problemet i måten den sorterer matriseelementene på. Standard sorter() i JavaScript bruker innsettings sortering by V8-motor av Chrome og Slå sammen sortering by Mozilla Firefox og Safari.

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

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

Hva er rask sortering?

Rask sortering følger Splitt og hersk algoritme. Det deler elementer inn i mindre deler basert på en eller annen tilstand og utfører sorteringsoperasjonene på de delte mindre delene. Derfor fungerer det bra for store datasett. Så her er trinnene for hvordan hurtigsortering fungerer i enkle ord.

1. Velg først et element som skal kalles som Pivot element.
2. 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 pivotelementet er til høyre.
3. Til slutt, utfør de samme operasjonene på venstre og høyre sideelementer til pivotelementet.

Så det er den grunnleggende omrisset av rask sortering. Her er trinnene som må følges en etter en for å utføre hurtigsortering.

Hvordan fungerer QuickSort

1. Finn først "dreie" element i matrisen.
2. Start den venstre pekeren ved det første elementet i matrisen.
3. Start høyre peker ved siste element i matrisen.
4. Sammenlign elementet som peker med venstre peker, og hvis det er mindre enn pivotelementet, flytt venstre peker til høyre (legg til 1 til venstre indeks). Fortsett dette til venstre sideelement er større enn eller lik dreieelementet.
5. Sammenlign elementet som peker med høyre peker, og hvis det er større enn pivotelementet, flytt høyre peker til venstre (trekk fra 1 til høyre indeks). Fortsett dette til høyre sideelement er mindre enn eller lik dreieelementet.
6. Sjekk om venstre peker er mindre enn eller lik høyre peker, og bytt deretter elementene på plassering av disse pekerne.
7. Øk venstre peker og reduser høyre peker.
8. Hvis indeksen til venstre peker fortsatt er mindre enn indeksen til høyre peker, gjenta prosessen; ellers returnerer 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 Pivot-elementet

Men før du går videre med Hurtigsortering, spiller valg av pivotelement en stor rolle. Hvis du velger det første elementet som pivotelement, gir det dårligst ytelse i den sorterte matrisen. Så det er alltid tilrådelig å velge det midterste elementet (lengden på arrayet delt på 2) som pivotelementet, og vi gjør det samme.

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

TRINN 1: Bestem pivot som midtelement. Så, 7 er pivotelementet.

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

TRINN 3: Sammenlign element på venstre peker med pivotelementet. Siden 5 < 6 flytter venstre peker til høyre for å indeksere 1.

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

TRINN 5: Sammenlign nå verdien på høyre peker med pivotelementet. Siden 9 > 6 flytt høyre peker til venstre. Stopp nå som 2 < 6 å flytte høyre peker.

TRINN 6: Bytt begge verdiene som finnes på venstre og høyre pekere med hverandre.

TRINN 7: Flytt begge pekerne ett trinn til.

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

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

Kode for å bytte to tall inn 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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //swap two elements
            i++;
            j--;
        }
    }
    return i;
}

Utfør den rekursive operasjonen

Når du har utført trinnene ovenfor, returneres indeksen til venstre peker, og vi må bruke den til å dele opp matrisen og utføre hurtigsortering på den delen. Derfor kalles det Divide and Conquer-algoritmen.

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

OBS: Rask sortering utføres på samme array og ingen nye arrays opprettes i prosessen.

Så vi må kalle dette skillevegg() forklart ovenfor og basert på det deler vi matrise inn 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 partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var result = quickSort(items, 0, items.length - 1);

Fullfør hurtigsorteringskode

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 element
        i       = left, //left pointer
        j       = right; //right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); //sawpping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}
// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray); //prints [2,3,5,6,7,9]

NOTAT: Rask sortering kjører med tidskompleksiteten til O(nlogn).