QuickSort-algoritme in JavaScript

Wat is snel sorteren?

Snel sorteren algoritme volgt de verdeel en heers-aanpak. Het verdeelt elementen in kleinere delen op basis van een bepaalde voorwaarde en voert de sorteerbewerkingen uit op die verdeelde kleinere delen.

Het Quick Sort-algoritme is een van de meest gebruikte en populaire algoritmen in elke programmeertaal. Maar als u een JavaScript-ontwikkelaar bent, heeft u er misschien wel eens van gehoord soort() die al beschikbaar is in JavaScript. Dan heb je misschien nagedacht over de noodzaak van dit Quick Sort-algoritme. Om dit te begrijpen, hebben we eerst nodig wat sorteren is en wat de standaardsortering is in JavaScript.

Wat is sorteren?

Sorteren is niets anders dan het rangschikken van elementen in de volgorde die wij willen. Misschien ben je dit tijdens je school- of studententijd tegengekomen. Zoals het rangschikken van getallen van kleiner naar groter (oplopend) of van groter naar kleiner (aflopend) is wat we tot nu toe zagen en heet sorteren.

Standaard sortering in JavaScript

Zoals eerder vermeld, heeft JavaScript dat wel 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.

Standaard sortering in JavaScript

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. Hier zijn dus de stappen hoe Snel sorteren in eenvoudige woorden werkt.

  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 rechterzijelementen op het draaielement.

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.

Hoe werkt QuickSort

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 het element bij de linkeraanwijzer met het draaielement. Omdat 5 <6 de linkerwijzer naar rechts verschuift naar index 1.

STAP 4: Nu nog steeds 3 <6, dus verschuif de linkerwijzer naar nog een index naar rechts. Dus nu stopt 7 > 6 met het verhogen van de linkeraanwijzer en nu staat de linkeraanwijzer 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 in JavaScript te verwisselen

verwissel twee getallen 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

Code om de partitie uit te voeren

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,

Recursieve bewerking

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]

Snel sorteren

NOTITIE: Snel sorteren werkt met de Time Complexheid van O(nlogn).