QuickSort-algoritme in JavaScript met voorbeeld

Wat is snel sorteren?

Snel sorteren is een vergelijkingssorteeralgoritme dat de volgende stappen volgt: Verdeel en heers Deze aanpak selecteert één element als spil, verdeelt de array in een deel met waarden kleiner dan de spil en een deel met waarden groter dan de spil, en past vervolgens dezelfde procedure toe op elk deel totdat de hele array is geordend.

Quick Sort is een van de meest gebruikte sorteeralgoritmes in elke programmeertaal. Als je schrijft JavaScriptJe hebt waarschijnlijk de ingebouwde functie al gebruikt. soort() methode, dus je vraagt ​​je misschien af ​​waarom het de moeite waard is om een ​​aparte Quick Sort-implementatie te leren. Om die vraag te beantwoorden, moet je eerst weten wat sorteren inhoudt en wat de standaard sorteermethode inhoudt. JavaHet script doet dat inderdaad.

Quick Sort wordt door drie eigenschappen gedefinieerd:

• In plaats daarvan: Het herschikt het origineel. reeks en maakt geen tweede array van dezelfde grootte aan.
• Recursief: Elke partitie produceert twee kleinere bereiken die op dezelfde manier gesorteerd worden.
• onstabiel: Twee elementen met dezelfde sleutel kunnen uiteindelijk in een andere relatieve volgorde terechtkomen dan waarin ze begonnen.

Wat is sorteren?

Sorteren betekent elementen in een bepaalde volgorde plaatsen. Je bent dit vrijwel zeker al eens op school tegengekomen: getallen van klein naar groot rangschikken is... oplopende volgorde, en ze van groot naar klein plaatsen is aflopend volgorde. Sorteren is niet beperkt tot getallen. Tekstreeksen kunnen alfabetisch worden gesorteerd, datums chronologisch en objecten op basis van elk gewenst veld, zoals prijs of score.

Sorteren is belangrijk omdat geordende data snellere bewerkingen mogelijk maakt. Een binaire zoekopdracht heeft een tijdsbestek van O(log n), maar alleen met gesorteerde invoer. Het verwijderen van duplicaten, bereikquery's, rangschikking en samenvoegingsbewerkingen worden allemaal veel goedkoper zodra de data geordend is. Daarom bevat elke programmeertaal minstens één sorteerfunctie.

Standaard sortering in JavaScript

Zoals eerder gezegd, JavaHet script biedt soort()Neem een ​​kleine array, bijvoorbeeld [5,3,7,6,2,9], die je in oplopende volgorde wilt hebben. Roep de functie aan. soort() De array lijkt precies dat te doen.

De bovenstaande schermafbeelding toont de browserconsole die de gesorteerde array afdrukt. Hier is dezelfde code:

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

Output:

[ 2, 3, 5, 6, 7, 9 ]

Dat resultaat klopt, maar is slechts toevallig. Array.prototype.sort() zet elk element om in een tekenreeks en vergelijkt de tekenreeksen. Tenzij je een vergelijkingsfunctie opgeeft. Elke waarde in deze array is een enkel cijfer, dus de tekenreeksvolgorde komt toevallig overeen met de numerieke volgorde. Verander de gegevens en de illusie verdwijnt.

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Output:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

Welk algoritme gebruikt sort()?

De specificatie noemt geen specifiek algoritme, dus elke engine kiest zijn eigen algoritme. Moderne engines gebruiken allemaal een op samenvoeging gebaseerd algoritme:

• V8 (Chrome, Edge, Node.js) heeft gebruikt TimSorteren Sinds de V8 7.0, geleverd in Chrome 70.
• Spinnenaap (Firefox) toepassingen voeg soort samen.
• JavaScriptCore (Safari) gebruikt ook voeg soort samen.

Sinds ES2019 garandeert de taal dat sort() is stabielDit sluit een eenvoudige Quick Sort in de engine uit. Sorteren op basis van samenvoeging vereist O(n) hulpgeheugen en moet uw functie aanroepen. JavaScriptvergelijker voor elke afzonderlijke vergelijking. Een handgeschreven numerieke Quick Sort vergelijkt getallen direct en sorteert op hun plaats, waardoor deze kan winnen bij grote numerieke arrays. Het sorteren van 1,000,000 willekeurige gehele getallen in Node.js 22 duurde ongeveer 100 ms met de snelle sorteerfunctie hieronder en ongeveer 210 ms with sort((a, b) => a - b).

Quick Sort is dus de moeite waard om te leren als je in-place sortering nodig hebt, strakke controle over het geheugen, of gewoon een goed begrip van hoe sorteren werkt. Laten we de mechanismen eens nader bekijken.

Hoe werkt Quick Sort?

Quick Sort herhaalt één kernbewerking, genaamd partitionering, op steeds kleinere afstanden. Hier volgen de stappen in de juiste volgorde:

1. Vind de spil element in de array.
2. Plaats de linker aanwijzer bij het eerste element van het bereik.
3. Plaats de rechter aanwijzer bij het laatste element van het bereik.
4. Vergelijk het element bij de linker aanwijzer met het spilpunt. Als het kleiner is dan het spilpunt, verplaats je de linker aanwijzer één stap naar rechts. Ga zo door totdat het linker element groter is dan of gelijk aan het spilpunt.
5. Vergelijk het element bij de rechter aanwijzer met het spilpunt. Als het groter is dan het spilpunt, verplaats je de rechter aanwijzer één stap naar links. Ga zo door totdat het element bij de rechter aanwijzer kleiner of gelijk is aan het spilpunt.
6. Als de linker aanwijzer nog steeds kleiner dan of gelijk is aan de rechter aanwijzer, verwissel dan de twee elementen.
7. Verhoog de linkeraanwijzer en verlaag de rechteraanwijzer.
8. Als de linkerindex nog steeds kleiner dan of gelijk is aan de rechterindex, herhaal dan vanaf stap 4. Retourneer anders de index van de linkeraanwijzer.

Het bovenstaande diagram tracDit zijn de bewegingen van de aanwijzer op een voorbeeldarray. Elk element dat kleiner is dan het spilpunt komt links daarvan terecht en elk groter element komt rechts daarvan terecht, wat precies overeenkomt met de geretourneerde index. In het onderstaande gedeelte wordt dezelfde array stap voor stap doorlopen.

Hoe bepaal je het spil-element?

Het kiezen van het pivotpunt is de enige beslissing die een snelle Quick Sort onderscheidt van een trage. Als je altijd de eerste Als we een element toevoegen aan een reeds gesorteerde array, ontstaat de slechtst mogelijke splitsing: een lege kant en een kant met alle resterende elementen. Daardoor wordt het algoritme O(n²). midden Het element (de lengte van de array gedeeld door twee) voorkomt die valkuil voor gesorteerde en omgekeerd gesorteerde invoer, en daarom gebruikt de onderstaande code het.

Veelgebruikte pivotstrategieën:

• Eerste of laatste element: Het eenvoudigst te coderen, maar O(n²) op gesorteerde gegevens.
• Middelste element: Een goede standaardmethode die gesorteerde en omgekeerd gesorteerde arrays in O(n log n) verwerkt.
• Willekeurig element: Hierdoor is het onmogelijk om de worst-case input van tevoren te construeren.
• Mediaan van drie: berekent de mediaan van de eerste, middelste en laatste waarde; de ​​standaardkeuze in productiebibliotheken.

Loop nu de Quick Sort-procedure door op de array. [5,3,7,6,2,9].

STAP 1: Het spilpunt is het middelste element. Met links = 0 en rechts = 5, Math.floor((5 + 0) / 2) geeft index 2, dus de pivotwaarde is 7.

STAP 2: Begin de pointers aan de uiteinden van de array. De linker pointer bevindt zich op index 0 (waarde). 5) en de rechter aanwijzer bevindt zich op index 5 (waarde 9).

STAP 3: Vergelijk de linkerwaarde met het spilpunt. 5 < 7, dus ga naar rechts naar index 1. 3 < 7, dus ga naar rechts naar index 2. De waarde daar is 7, wat niet kleiner is dan het spilpunt, dus de linkerwijzer stopt bij index 2.

STAP 4: Vergelijk de rechterwaarde met het spilpunt. 9 > 7, dus ga naar links naar index 4. De waarde daar is 2, wat niet groter is dan het spilpunt, dus de rechterwijzer stopt bij index 4.

STAP 5: De linkerindex (2) is kleiner dan of gelijk aan de rechterindex (4), dus verwissel de twee waarden. De array wordt [5,3,2,6,7,9].

STAP 6: Verplaats beide aanwijzers één stap naar binnen. De linker aanwijzer staat nu op index 3 en de rechter aanwijzer ook op index 3.

STAP 7: Herhaal de scan. De waarde op index 3 is 6, en 6 < 7, dus de linker aanwijzer schuift door naar index 4. De waarde op index 3 is niet groter dan het spilpunt, dus de rechter aanwijzer blijft op index 3 staan.

STAP 8: De linkerindex (4) is nu groter dan de rechterindex (3), dus de lus eindigt en de functie retourneert 4Alles vóór index 4 is kleiner dan of gelijk aan het draaipunt, en alles vanaf index 4 is groter dan of gelijk aan het draaipunt.

Op basis van die stappenplan heb je code nodig voor twee bewerkingen: swappen.ping twee elementen en het verdelen van een bereik.

Code om er twee te ruilen Numbers in JavaScript

Zoals de bovenstaande schermafbeelding van de editor laat zien, gebruikt de swap-helper een tijdelijke variabele om de waarden op twee indexen te verwisselen. Het wijzigt de array direct en retourneert niets.

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

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Output:

[ 9, 3, 7, 6, 2, 5 ]

Code De partitie uitvoeren

De code in de bovenstaande schermafbeelding zet stappen 1 tot en met 8 om in een functie. De twee binnenste loops schuif de aanwijzers op, de if Het blok voert de wisseling uit en de functie retourneert de splitsingsindex.

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

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Output:

[ 5, 3, 2, 6, 7, 9 ]
4

De uitvoer komt exact overeen met de handmatige stappen: na één partitie-doorgang is de array [5,3,2,6,7,9] en de geretourneerde splitsingsindex is 4.

Voer de recursieve bewerking uit Operatie

Zodra de partitionering de splitsingsindex oplevert, gebruik je deze om het bereik te verdelen en voer je Quick Sort uit op elke helft. Daarom wordt het een verdeel-en-heersalgoritme genoemd. De recursie gaat door totdat elk deelbereik één element bevat, waarna de hele array gesorteerd is.

Let op: Quick Sort werkt gedurende het hele proces met dezelfde array. Er worden geen nieuwe arrays aangemaakt, wat het een in-place algoritme maakt.

Dus je belt de partitie () De hierboven uitgelegde functie gebruiken om de retourwaarde te splitsen. reeks in delen. Hier is de code die dat doet:

Let op de twee bewakingsvoorwaarden die in de schermafbeelding zijn gemarkeerd. left < index - 1 bevestigt dat er aan de linkerkant ten minste twee elementen overblijven, en index < right Dit bevestigt hetzelfde voor de rechterkant. Zonder die beveiligingen zou de functie zichzelf oneindig blijven aanroepen bij bereiken met slechts één element.

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 items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Output:

[ 2, 3, 5, 6, 7, 9 ]

Voltooi de snelle sorteerfunctie Code

Door de onderdelen swap, partition en recursie samen te voegen, verkrijgt men de volledige implementatie:

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

Output:

[ 2, 3, 5, 6, 7, 9 ]

De bovenstaande schermafbeelding toont het complete programma in de editor, samen met de gesorteerde array in de console. Deze implementatie is getest met een reeds gesorteerde array, een omgekeerd gesorteerde array, arrays met dubbele en identieke waarden, negatieve getallen, een enkel element en een lege array, en levert in alle gevallen het juiste resultaat op.

Tijd- en ruimtecomplexiteit van Quick Sort

Elke partitiestap doorloopt elk element in het bereik één keer, dus een enkele stap kost O(n). De totale kosten hangen daarom af van hoe vaak de array kan worden opgesplitst voordat de bereiken triviaal worden.

De ruimtecomplexiteit is O(log n). Voor deze in-place-versie wordt geen tweede array toegewezen, dus het enige extra geheugen is de recursiestack, en gebalanceerde splitsing zorgt ervoor dat die stack ongeveer log₂(n) frames diep blijft. In het ergste geval groeit de stack tot O(n) frames, waardoor zeer grote arrays de aanroepstack kunnen overlopen.

Twee getallen maken dit concreet. Het sorteren van 4,096 willekeurige waarden met de bovenstaande code gebruikte ongeveer 65,000 vergelijkingen, terwijl de theoretische n·log₂(n) 49,152 bedraagt. De diepste recursie bereikte 24 frames, terwijl log₂(4096) 12 frames is. Beide getallen vallen binnen de kleine constante factor die verwacht wordt van een O(n log n) algoritme.

Quick Sort versus andere sorteermethoden Algorithms

Quick Sort is zelden de enige optie. De onderstaande tabel vergelijkt het met andere algoritmes die je waarschijnlijk zult tegenkomen, zodat je het juiste algoritme voor jouw data kunt kiezen.

Quick Sort wint in de praktijk meestal omdat de binnenste lus compact is en het werkt met cachevriendelijke, aaneengesloten bereiken. Kies voor merge sort wanneer je een gegarandeerde O(n log n)-grens of stabiele ordening nodig hebt, heap sort wanneer het geheugen zeer beperkt is en insertion sort voor zeer kleine of bijna gesorteerde arrays. Productiebibliotheken combineren ze vaak: introsort begint met Quick Sort, schakelt over naar heap sort als de recursie te diep wordt en eindigt met insertion sort voor kleine bereiken.

Hoe je objecten en tekenreeksen snel kunt sorteren

De tot nu toe getoonde implementatie vergelijkt waarden met < en >, wat het beperkt tot getallen. Echte toepassingen moeten sorteren. objecten op basis van een eigenschap, alfabetische volgorde van tekenreeksen of chronologische volgorde van datums. De oplossing is om de vergelijking naar een callback te verplaatsen, precies zoals de ingebouwde functie. sort() doet.

Een comparator ontvangt twee waarden en retourneert een negatief getal wanneer de eerste waarde eerst zou moeten komen, een positief getal wanneer de tweede waarde eerst zou moeten komen, en nul wanneer de twee gelijk zijn. Door de twee vastgelegde vergelijkingen te vervangen door aanroepen van de comparator werkt het algoritme met elk gegevenstype.

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Output:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

Drie details zijn het vermelden waard. De recursiebeveiliging is nu left >= right, wat correct is voor elk bereik en niet afhankelijk is van de lengte van de buitenste array. Stringvergelijking maakt gebruik van localeCompare() zodat geaccentueerde tekens en hoofdlettergevoeligheid correct worden verwerkt in plaats van door de ruwe codepunten. En omdat Quick Sort niet stabiel is, kunnen records met hetzelfde salaris van plaats wisselen; sorteer op een tweede sleutel die de doorslag geeft als de oorspronkelijke volgorde voor u belangrijk is.

Klaar om verder te gaan? Versterk de basis met de JavaScriptintroductieOefen de aanwijzermechanismen in JavaScriptlussenwerk meer door praktisch JavaScriptcodevoorbeeldenvergelijk implementaties in Invoegsortering en Heap Sorteren, of voeg statische typen toe aan dit algoritme met de TypeScript referentie.

Veelgestelde vragen