Die schnelle Sortierung ist ein hocheffizienter Sortieralgorithmus und basiert auf der Partitionierung von Datenarrays in kleinere Arrays. Ein großes Array wird in zwei Arrays aufgeteilt, von denen eines Werte enthält, die kleiner als der angegebene Wert sind, z. B. Pivot, basierend auf dem die Partition erstellt wird, und ein anderes Array Werte enthält, die größer als der Pivot-Wert sind.
Quicksort-Partitionen an Array und ruft sich dann zweimal rekursiv auf, um die beiden resultierenden Subarrays zu sortieren. Dieser Algorithmus ist für große Datenmengen sehr effizient, da seine durchschnittliche und Worst-Case-Komplexität O (n2) beträgt.
Partition in Quick Sort
Die folgende animierte Darstellung erklärt, wie So finden Sie den Pivot-Wert in einem Array.
Der Pivot-Wert unterteilt die Liste in zwei Teile. Und rekursiv finden wir den Pivot für jede Unterliste, bis alle Listen nur ein Element enthalten.
Pivot-Algorithmus für die schnelle Sortierung
Basierend auf unserem Verständnis der Partitionierung bei der schnellen Sortierung werden wir dies tun Versuchen Sie nun, einen Algorithmus dafür zu schreiben, der wie folgt lautet:
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
Pivot-Pseudocode für schnelle Sortierung
Der Pseudocode für den obigen Algorithmus kann abgeleitet werden als –
Schnellsortierungsalgorithmus
Wenn wir den Pivot-Algorithmus rekursiv verwenden, erhalten wir kleinere mögliche Partitionen. Jede Partition wird dann zur schnellen Sortierung verarbeitet. Wir definieren den rekursiven Algorithmus für Quicksort wie folgt:
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
Pseudocode für schnelle Sortierung
Um mehr darüber zu erfahren, lesen Sie den Pseudocode für schnell Sortieralgorithmus –
Um mehr über die schnelle Sortierimplementierung in der Programmiersprache C zu erfahren, klicken Sie bitte hier.