QuickSort Algoritm in JavaScript

Vad är sortering?

Sortering är inget annat än att ordna element i den ordning vi vill. Du kanske har stött på detta under din skol- eller högskoletid. Som att ordna siffror från mindre till större (stigande) eller från större till mindre (fallande) är vad vi sett hittills och kallas sortering.

Standardinställning JavaScript

Som tidigare nämnts, JavaManus har sortera(). Låt oss ta ett exempel med få array av element som [5,3,7,6,2,9] och vill sortera dessa arrayelement i stigande ordning. Bara ring sortera() på objektmatris och den sorterar matriselement i stigande ordning.

Code:

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

Vad är anledningen till att välja Quick sort över standard sort() in JavaScript

Även om sort() ger det resultat vi vill ha, ligger problemet i hur det sorterar arrayelementen. Standard sort() in JavaScript använder insättningssortering by V8 Engine of Chrome och Slå samman sortering by Mozilla Firefox och Safari.

Men i övrigt är detta inte lämpligt om du behöver sortera ett stort antal element. Så lösningen är att använda snabbsortering för stora datamängder.

Så för att förstå helt måste du veta hur Quick sortering fungerar och låt oss se det i detalj nu.

Vad är snabbsortering?

Snabb sortering följer Söndra och erövra algoritm. Det är att dela in element i mindre delar baserat på något tillstånd och utföra sorteringsoperationerna på de uppdelade mindre delarna. Därför fungerar det bra för stora datamängder. Så här är stegen hur Snabbsortering fungerar i enkla ord.

1. Välj först ett element som ska kallas som svängtappen elementet.
2. Jämför sedan alla arrayelement med det valda pivotelementet och arrangera dem på ett sådant sätt att element mindre än pivotelementet är till vänster och större än pivot är till höger.
3. Slutligen, utför samma operationer på vänster och höger sidoelement till pivotelementet.

Så, det är grundkonturen av Quick sort. Här är stegen som måste följas ett efter ett för att utföra snabbsortering.

Hur fungerar QuickSort

1. Hitta först "svänga" element i arrayen.
2. Starta den vänstra pekaren vid det första elementet i arrayen.
3. Starta den högra pekaren vid det sista elementet i arrayen.
4. Jämför elementet som pekar med vänster pekare och om det är mindre än pivotelementet, flytta sedan den vänstra pekaren till höger (lägg till 1 till vänster index). Fortsätt tills det vänstra sidoelementet är större än eller lika med pivotelementet.
5. Jämför elementet som pekar med högerpekaren och om den är större än pivotelementet, flytta då högerpekaren åt vänster (subtract 1 till höger index). Fortsätt detta tills elementet på höger sida är mindre än eller lika med pivotelementet.
6. Kontrollera om den vänstra pekaren är mindre än eller lika med den högra pekaren, byt sedan elementen på platserna för dessa pekare.
7. Öka den vänstra pekaren och minska den högra pekaren.
8. Om index för vänster pekare fortfarande är mindre än index för höger pekare, upprepa sedan processen; annars returnerar indexet för den vänstra pekaren.

Så låt oss se dessa steg med ett exempel. Låt oss överväga en rad element som vi behöver sortera är [5,3,7,6,2,9].

Bestäm Pivot-elementet

Men innan du går vidare med snabbsorteringen spelar valet av pivotelementet en stor roll. Om du väljer det första elementet som pivotelement, ger det sämst prestanda i den sorterade arrayen. Så det är alltid tillrådligt att välja mittelementet (längden på arrayen dividerat med 2) som pivotelementet och vi gör detsamma.

Här är stegen för att utföra snabbsortering som visas med ett exempel [5,3,7,6,2,9].

STEG 1: Bestäm pivot som mittelement. Så, 7 är pivotelementet.

STEG 2: Starta vänster- och högerpekare som första respektive sista element i arrayen. Så vänsterpekaren pekar på 5 vid index 0 och höger pekare pekar på 9 på index 5.

STEG 3: Jämför element vid den vänstra pekaren med pivotelementet. Eftersom 5 < 6 flyttar vänster pekare åt höger till index 1.

STEG 4: Nu, fortfarande 3 <6 så flytta vänster pekare till ytterligare ett index åt höger. Så nu slutar 7 > 6 att öka den vänstra pekaren och nu är vänster pekare på index 2.

STEG 5: Jämför nu värdet på den högra pekaren med pivotelementet. Eftersom 9 > 6 flyttar den högra pekaren åt vänster. Nu som 2 < 6 sluta flytta den högra pekaren.

STEG 6: Byt båda värdena som finns på vänster och höger pekare med varandra.

STEG 7: Flytta båda pekarna ett steg till.

STEG 8: Eftersom 6 = 6, flytta pekarna till ett steg till och stanna när vänster pekare korsar den högra pekaren och returnerar indexet för den vänstra pekaren.

Så, här baserat på ovanstående metod, behöver vi skriva kod för swapping element och partitionering av arrayen enligt stegen ovan.

Code att byta ut två siffror JavaScript

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

Code för att utföra partitioneringen enligt stegen ovan

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 rekursiva operationen

När du har utfört ovanstående steg kommer index för den vänstra pekaren att returneras och vi måste använda det för att dela upp arrayen och utföra snabbsorteringen på den delen. Därför kallas det Divide and Conquer-algoritm.

Så snabbsortering utförs tills alla element i den vänstra arrayen och den högra arrayen är sorterade.

Obs: Snabbsortering utförs på samma array och inga nya arrayer skapas i processen.

Så vi måste kalla detta dela() förklaras ovan och utifrån det delar vi upp array in i delar. Så här är koden där du använder 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);

Komplett snabbsorteringskod

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]

OBS: Snabbsortering körs med tidskomplexiteten på O(nlogn).