QuickSort-algoritme in JavaScript

Wat is sorteren?

Sorteren is niets anders dan het ordenen van elementen in de volgorde die we willen. Je bent dit misschien wel eens tegengekomen op school of op de universiteit. Net zoals het ordenen van getallen van kleiner naar groter (oplopend) of van groter naar kleiner (aflopend) is wat we tot nu toe zagen en dat wordt sorteren genoemd.

Standaard sortering JavaScript

Zoals eerder gezegd, JavaScript heeft soort(). Laten we een voorbeeld nemen met een paar array-elementen zoals [5,3,7,6,2,9] en deze array-elementen in oplopende volgorde willen sorteren. Bel gewoon soort() on items array en sorteert array-elementen in oplopende volgorde.

Code:

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

Wat is de reden om Snel sorteren te verkiezen boven standaard sort() in JavaScript

Hoewel sort() het gewenste resultaat oplevert, ligt het probleem bij de manier waarop de array-elementen worden gesorteerd. Standaard sort() in JavaScript gebruikt invoegsoort by V8-motor van chroom en Samenvoegen sorteren by mozilla Firefox en Safari.

Maar verder is dit niet geschikt als u een groot aantal elementen moet sorteren. De oplossing is dus om Snel sorteren te gebruiken voor grote datasets.

Om het volledig te begrijpen, moet u dus weten hoe Snel sorteren werkt en laten we dat nu in detail zien.

Wat is Snel sorteren?

Snel sorteren volgt Verdeel en heers algoritme. Het verdeelt elementen in kleinere delen op basis van een bepaalde voorwaarde en voert de sorteerbewerkingen uit op die verdeelde kleinere delen. Daarom werkt het goed voor grote datasets. Dus, hier zijn de stappen hoe Quick sort werkt in simpele woorden.

1. Selecteer eerst een element dat moet worden aangeroepen als spil element.
2. Vergelijk vervolgens alle array-elementen met het geselecteerde pivot-element en rangschik ze op een zodanige manier dat elementen die kleiner zijn dan het pivot-element zich links bevinden en groter dan het pivot-element rechts zijn.
3. Voer ten slotte dezelfde handelingen uit op de linker- en rechterelementen van het draaipuntelement.

Dat is dus het basisoverzicht van Snel sorteren. Hier zijn de stappen die één voor één moeten worden gevolgd om Snel sorteren uit te voeren.

Hoe werkt QuickSort

1. Zoek eerst de "scharnier" element in de array.
2. Start de linkeraanwijzer op het eerste element van de array.
3. Start de rechteraanwijzer op het laatste element van de array.
4. Vergelijk het element dat wijst met de linkeraanwijzer en als het kleiner is dan het draaielement, verplaats dan de linkeraanwijzer naar rechts (voeg 1 toe aan de linkerindex). Ga hiermee door totdat het linker zijelement groter is dan of gelijk is aan het scharnierelement.
5. Vergelijk het element dat wijst met de rechteraanwijzer en als het groter is dan het draaielement, verplaats dan de rechteraanwijzer naar links (trek 1 af van de rechterindex). Ga hiermee door totdat het rechterzij-element kleiner is dan of gelijk is aan het draaielement.
6. Controleer of de linkeraanwijzer kleiner is dan of gelijk is aan de rechteraanwijzer en verwissel vervolgens de elementen op de locatie van deze aanwijzers.
7. Verhoog de linkeraanwijzer en verlaag de rechteraanwijzer.
8. Als de index van de linkerwijzer nog steeds kleiner is dan de index van de rechterwijzer, herhaal dan het proces; retourneer anders de index van de linkeraanwijzer.

Laten we deze stappen dus met een voorbeeld bekijken. Laten we eens kijken naar de reeks elementen die we moeten sorteren is [5,3,7,6,2,9].

Bepaal het draaielement

Maar voordat u verder gaat met de snelle sortering, speelt het selecteren van het draaielement een belangrijke rol. Als u het eerste element als draaielement selecteert, levert dit de slechtste prestaties op in de gesorteerde array. Het is dus altijd raadzaam om het middelste element (lengte van de array gedeeld door 2) als draaielement te kiezen en we doen hetzelfde.

Hier zijn de stappen om Snel sorteren uit te voeren, die wordt getoond met een voorbeeld [5,3,7,6,2,9].

STAP 1: Bepaal het spilpunt als middenelement. Dus, 7 is het draaielement.

STAP 2: Start de linker- en rechteraanwijzers respectievelijk als eerste en laatste elementen van de array. De linkerwijzer wijst dus naar 5 bij index 0 en de rechterwijzer wijst naar 9 op index5.

STAP 3: Vergelijk element bij de linker pointer met het pivot element. Aangezien 5 < 6 de linker pointer naar rechts verschuift naar index 1.

STAP 4: Nu, nog steeds 3 <6 dus verschuif de linker pointer naar nog een index naar rechts. Dus nu 7 > 6 stop met het verhogen van de linker pointer en nu staat de linker pointer op index 2.

STAP 5: Vergelijk nu de waarde bij de rechteraanwijzer met het draaielement. Omdat 9 > 6 de rechteraanwijzer naar links verplaatst. Als 2 < 6 nu stopt met het verplaatsen van de rechterwijzer.

STAP 6: Verwissel beide waarden die aanwezig zijn bij de linker- en rechteraanwijzers met elkaar.

STAP 7: Verplaats beide aanwijzers nog een stap.

STAP 8: Aangezien 6 = 6, verplaatst u de wijzers naar nog een stap en stopt u wanneer de linkerwijzer de rechterwijzer kruist en retourneert u de index van de linkerwijzer.

Dus hier, op basis van de bovenstaande aanpak, moeten we code schrijven voor het verwisselen van elementen en het partitioneren van de array, zoals vermeld in de bovenstaande stappen.

Code om twee getallen om te wisselen in JavaScript

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

Code om de partitie uit te voeren zoals vermeld in de bovenstaande stappen

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;
}

Voer de recursieve bewerking uit

Zodra u bovenstaande stappen heeft uitgevoerd, wordt de index van de linkeraanwijzer geretourneerd en moeten we die gebruiken om de array te verdelen en de snelle sortering op dat deel uit te voeren. Daarom wordt het het Divide and Conquer-algoritme genoemd.

Er wordt dus snel gesorteerd totdat alle elementen in de linkerarray en de rechterarray zijn gesorteerd.

Opmerking: Er wordt snel gesorteerd op dezelfde array en er worden geen nieuwe arrays gemaakt tijdens het proces.

We moeten dit dus bellen partitie () hierboven uitgelegd en op basis daarvan verdelen we de reeks in delen. Dus hier is de code waar je hem gebruikt,

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);

Volledige snelsorteercode

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]

NOTITIE: Snelle sortering wordt uitgevoerd met de tijdcomplexiteit van O(nlogn).