QuickSort-algoritme in JavaScript

Wat is snel sorteren?

Het Quick Sort- algoritme volgt de Divide and Conquer-benadering. Het verdeelt elementen in kleinere delen op basis van een bepaalde conditie 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 misschien wel eens gehoord van sort () dat al beschikbaar is in JavaScript. Dan dacht je misschien aan wat de behoefte is aan dit Quick Sort-algoritme. Om dit te begrijpen, hebben we eerst wat sortering is en wat de standaardsortering in JavaScript is.

Wat is sorteren?

Sorteren is niets anders dan elementen rangschikken in de volgorde die we willen. Je bent dit misschien tegengekomen in je school- of studententijd. Zoals het rangschikken van getallen van kleiner naar groter (oplopend) of van groter naar kleiner (aflopend) is wat we tot nu toe zagen en wordt het sorteren genoemd.

Standaard sortering in JavaScript

Zoals eerder vermeld, heeft JavaScript sort () . Laten we een voorbeeld nemen met een paar array-elementen zoals [5,3,7,6,2,9] en we willen deze array-elementen in oplopende volgorde sorteren. Roep gewoon sort () aan op items-array en het 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 kiezen boven standaard sorteren () in JavaScript

Hoewel sort () het gewenste resultaat geeft, ligt het probleem bij de manier waarop de array-elementen worden gesorteerd. Standaard sorteren () in JavaScript gebruikt invoegsortering door V8-engine van Chrome en samenvoegsortering door Mozilla Firefox en Safari .

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

Dus om volledig te begrijpen, moet u weten hoe Quick sort werkt en laat ons dat nu in detail bekijken.

Wat is Snel sorteren?

Snel sorteren volgt het Divide and Conquer- algoritme. Het verdeelt elementen in kleinere delen op basis van een bepaalde conditie en voert de sorteerbewerkingen uit op die verdeelde kleinere delen. Daarom werkt het goed voor grote datasets. Dit zijn dus de stappen voor hoe Snel sorteren werkt in eenvoudige bewoordingen.

Selecteer eerst een element dat als pivot- element moet worden genoemd .
Vergelijk vervolgens alle array-elementen met het geselecteerde pivot-element en rangschik ze zo dat elementen die kleiner zijn dan het pivot-element zich links bevinden en groter dan pivot rechts.
Voer ten slotte dezelfde bewerkingen uit op de linker- en rechterzijelementen van het scharnierelement.

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

Hoe werkt QuickSort

Zoek eerst het "pivot" -element in de array.
Start de linkeraanwijzer bij het eerste element van de array.
Start de rechter pointer bij het laatste element van de array.
Vergelijk het element dat met de linkeraanwijzer wijst en als het minder is dan het draai-element, 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.
Vergelijk het element dat met de rechterwijzer wijst en als het groter is dan het draai-element, verplaats dan de rechterwijzer naar links (trek 1 af van de rechterindex). Ga hiermee door totdat het rechter zijelement kleiner is dan of gelijk is aan het scharnierelement.
Controleer of de linkerwijzer kleiner is dan of gelijk is aan de rechterwijzer, en zaag de elementen op de locaties van deze aanwijzers.
Verhoog de linker aanwijzer en verlaag de rechter aanwijzer.
Als de index van de linkerwijzer nog steeds kleiner is dan de index van de rechterwijzer, herhaal dan het proces; anders retourneert de index van de linker aanwijzer.

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

Bepaal het draaipunt

Maar voordat we verder gaan met de snelle sortering, speelt het selecteren van het pivot-element een grote rol. Als u het eerste element als het pivot-element selecteert, geeft dit de slechtste prestaties in de gesorteerde array. Het is dus altijd aan te raden om het middelste element (lengte van de array gedeeld door 2) als het pivot-element te kiezen en we doen hetzelfde.

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

STAP 1: Bepaal het draaipunt als middelste element. Dus, 7 is het scharnierelement.

STAP 2: Start de linker- en rechterwijzers als respectievelijk eerste en laatste elementen van de array. Dus de linkerwijzer wijst naar 5 bij index 0 en de rechterwijzer wijst naar 9 bij index 5.

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

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

STAP 5: Vergelijk nu de waarde aan de rechterkant met het pivot-element. Aangezien 9> 6 de rechterwijzer naar links verplaatsen. Stop nu als 2 <6 met het verplaatsen van de rechterwijzer.

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

STAP 7: Verplaats beide wijzers nog een stap.

STAP 8: Sinds 6 = 6, verplaats de aanwijzers naar nog een stap en stop als de linkeraanwijzer de rechteraanwijzer kruist en de index van de linkeraanwijzer retourneert.

Dus, hier gebaseerd op de bovenstaande benadering, moeten we code schrijven voor het uitwisselen van elementen en het partitioneren van de array zoals vermeld in bovenstaande stappen.

Code om twee nummers in JavaScript te wisselen:

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 bovenstaande stappen:

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

Voer de recursieve bewerking uit

Nadat 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 onderdeel uit te voeren. Daarom wordt het het Divide and Conquer-algoritme genoemd.

Snel sorteren wordt dus uitgevoerd totdat alle elementen in de linker array en rechter array zijn gesorteerd.

Opmerking: Snel sorteren wordt uitgevoerd op dezelfde array en er worden geen nieuwe arrays gemaakt tijdens het proces.

Dus we moeten deze partitie () aanroepen zoals hierboven uitgelegd en op basis daarvan verdelen we de array in delen. Dus hier is de code waar u deze gebruikt,

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

Volledige snelle sorteercode:

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]