Snel sorteren is een zeer efficiënt sorteeralgoritme en is gebaseerd op het partitioneren van een reeks gegevens in kleinere arrays. Een grote array is opgedeeld in twee arrays waarvan er één waarden bevat die kleiner zijn dan de opgegeven waarde, zeg pivot, op basis waarvan de partitie is gemaakt en een andere array waarden bevat die groter zijn dan de pivotwaarde.
Quicksort-partities en array en roept zichzelf vervolgens tweemaal recursief aan om de twee resulterende subarrays te sorteren. Dit algoritme is tamelijk efficiënt voor datasets van grote omvang, aangezien de gemiddelde en worst-case complexiteit respectievelijk O (n2) zijn.
Partitie in Quick Sort
De volgende geanimeerde weergave legt uit hoe om de draaipuntwaarde in een array te vinden.
De draaipuntwaarde verdeelt de lijst in twee delen. En recursief vinden we het draaipunt voor elke sublijst totdat alle lijsten slechts één element bevatten.
Snel sorteren draaipuntalgoritme
Gebaseerd op ons begrip van partitionering bij snel sorteren, zullen we probeer er nu een algoritme voor te schrijven, dat is als volgt.
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
Quick Sort Pivot Pseudocode
De pseudocode voor het bovenstaande algoritme kan worden afgeleid als –
Quick Sort Algorithm
Door recursief pivot-algoritme te gebruiken, eindigen we met kleinere mogelijke partities. Elke partitie wordt vervolgens verwerkt om snel te sorteren. We definiëren een recursief algoritme voor quicksort als volgt –
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Quick Sort Pseudocode
Om er meer in te krijgen, bekijk de pseudocode voor een snelle sort algoritme –
Klik hier voor meer informatie over snelle sorteerimplementatie in programmeertaal C.