QuickSort-algoritm i JavaScript

Vad är snabb sortering?

Snabbsorteringsalgoritmen följer metoden Divide and Conquer. Den delar in element i mindre delar baserat på något tillstånd och utför sorteringsoperationerna på de delade mindre delarna.

Snabbsorteringsalgoritm är en av de mest använda och populära algoritmerna i alla programmeringsspråk. Men om du är en JavaScript-utvecklare kan du kanske höra sort () som redan finns i JavaScript. Då kanske du har tänkt på vad behovet av denna Quick Sort-algoritm är. För att förstå detta behöver vi först vad som är sortering och vad som är standardsortering i JavaScript.

Vad är sortering?

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

Standardsortering i JavaScript

Som nämnts tidigare har JavaScript sorterat () . Låt oss ta ett exempel med ett fåtal element som [5,3,7,6,2,9] och vill sortera dessa arrayelement i stigande ordning. Ring bara sort () på objektmatrisen och det sorterar matriselement i stigande ordning.

Koda:

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

Vad är anledningen att välja Snabbsortering över standardsortering () i JavaScript

Även om sort () ger det resultat vi vill ha, ligger problemet med hur det sorterar arrayelementen. Standardsortering () i JavaScript använder insättningssortering efter V8 Engine i Chrome och Sammanfoga sortering efter Mozilla Firefox och Safari .

Men ö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 dataset.

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

Vad är snabb sortering?

Snabb sortering följer algoritmen Divide and Conquer . Det delar in element i mindre delar baserat på något tillstånd och utför sorteringsoperationer på de delade mindre delarna. Därför fungerar det bra för stora datamängder. Så här är stegen hur snabb sortering fungerar i enkla ord.

Välj först ett element som ska kallas som pivotelement .
Därefter jämför alla arrayelement med det valda pivotelementet och ordna dem på ett sådant sätt att element som är mindre än pivotelementet är till vänster och större än pivot är till höger.
Slutligen, utför samma operationer på vänster och höger sidoelement till pivotelementet.

Så det är den grundläggande konturen för snabb sortering. Här är stegen som måste följas en efter en för att utföra snabbsortering.

Hur fungerar QuickSort

Hitta först "pivot" -elementet i matrisen.
Starta den vänstra pekaren vid det första elementet i matrisen.
Starta rätt pekare vid det sista elementet i matrisen.
Jämför elementet som pekar med vänster pekare och om det är mindre än pivotelementet, flytta sedan vänster pekare åt höger (lägg till 1 i det vänstra indexet). Fortsätt detta tills elementet till vänster är större än eller lika med pivotelementet.
Jämför elementet som pekar med högerpekaren och om det är större än pivotelementet, flytta sedan högerpekaren åt vänster (subtrahera 1 till höger index). Fortsätt detta tills elementet på höger sida är mindre än eller lika med pivotelementet.
Kontrollera om den vänstra pekaren är mindre än eller lika med den högra pekaren och såg sedan elementen på platsen för dessa pekare.
Öka den vänstra pekaren och minska den högra pekaren.
Om index för vänster pekare fortfarande är mindre än index för höger pekare, upprepa sedan processen; annars returnerar du indexet för den vänstra pekaren.

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

Bestäm svängelement

Men innan du går vidare med Snabbsorteringen spelar det en viktig roll att välja pivotelement. Om du väljer det första elementet som pivotelementet, ger det sämsta prestanda i den sorterade matrisen. Så det är alltid tillrådligt att välja mittelementet (längden på matrisen dividerat med 2) som ledelement 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 sväng som mittelement. Så 7 är ledelementet.

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

STEG 3: Jämför elementet till vänster med pivotelementet. Sedan flyttar 5 <6 vänster pekare åt höger till index 1.

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

STEG 5: Jämför nu värdet vid rätt pekare med pivotelementet. Sedan 9> 6 flyttar du högerpekaren åt vänster. Nu när 2 <6 slutar flytta höger pekare.

STEG 6: Byt båda värdena till vänster och höger med varandra.

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

STEG 8: Eftersom 6 = 6, flytta pekare till ytterligare ett steg och stoppa när vänster pekare korsar höger pekare och returnera index för vänster pekare.

Så här, baserat på ovanstående tillvägagångssätt, måste vi skriva kod för att byta element och partitionera matrisen som nämns i ovanstående steg.

Kod för att byta två nummer i JavaScript:

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

Kod för att utföra partitionen som nämns i ovanstående steg:

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 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 matrisen och utföra snabbsorteringen på den delen. Därför kallas det Divide and Conquer algoritm.

Så snabbsortering utförs tills alla element i vänster array och höger array sorteras.

Obs! Snabb sortering utförs på samma matris och inga nya matriser skapas under processen.

Så vi måste kalla den här partitionen () som förklarats ovan och baserat på att vi delar upp matrisen 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 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 snabb sorteringskod:

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]