Quicksort
Quicksort ist ein Sortieralgorithmus, der zum Sortieren von Elementen in einem Array verwendet wird. Er wurde 1959 von Tony Hoare entwickelt und ist auch heute noch weit verbreitet. Quicksort erstellt Partitionen innerhalb des Arrays, was im Wesentlichen bedeutet, dass es das Array in zwei Teile aufteilt und diese Teile dann weiter in weitere Teile aufteilt und dabei sortiert. Es führt die eigentliche Sortierung durch, da es sich um eine Vergleichssortierung handelt. Das bedeutet, dass sie einen Drehpunkt im Array auswählt und diesen dann mit allen anderen Punkten im Array vergleicht.
Animierte Visualisierung des Quicksort-Algorithmus. Die horizontalen Linien sind Pivot-Werte
Algorithmus
- Wählen Sie ein beliebiges Element im Array aus, dies wird nun der Drehpunkt sein.
- Partitionieren Sie die Elemente. Vergleichen Sie alle Elemente in der Anordnung mit dem Pivot, wobei diejenigen, die niedriger als der Pivot sind, nach links vom Pivot und alle Elemente in der Anordnung, die höher als der Pivot sind, nach rechts vom Pivot verschoben werden. Beachten Sie, dass sich unser Pivot jetzt in seiner sortierten Position befindet.
- Rückzug in die beiden Partitionen. Wenden Sie die obigen zwei Schritte auf die beiden Partitionen an, die wir in Schritt 2 erstellt haben.
Oft wird das Element ganz links als Drehpunkt gewählt. Die Rekursion bedeutet, dass der Algorithmus auf den beiden Partitionen, die durch die Vergleiche mit dem Pivot erzeugt wurden, exakt den gleichen Algorithmus ausführt. Beachten Sie, dass dieser Algorithmus die Partitionierung des Arrays in Unterarrays und die Aufteilung dieser Unterarrays in noch kleinere Unterarrays fortsetzt. Jedes Mal, wenn er dies tut, wählt er einen neuen Pivot innerhalb des Unterarrays und vergleicht die Elemente mit dem Unterarray. Der Basisfall ist, wenn der Algorithmus ein Unterarray mit nur einem Element erreicht, in dem er einfach anhält, weil ein Element nicht sortiert werden muss.
