Quick-Sort
Quick-Sort ist einer der bekanntesten Sortieralgorithmen, weil er sehr effizient ist. Leider ist er nicht besonders einfach. Es gibt ihn in vielen verschiedenen Varianten. Aus diesem Grund werdet ihr auch zahlreiche Implementierung finden, wenn ihr nach diesem Algorithmus sucht.
Zu Beginn wird ein Pivot-Element festgelegt. Dies ist ein Element, mit dem alle anderen Werte verglichen werden. Alles, was kleiner als dieser Wert ist, wird links im Array eingeordnet. Alles, was größer als dieser Wert ist, wird im rechten Teil des Arrays eingeordnet. Zur Bestimmung dieses Pivot-Elementes gibt es verschiedene Möglichkeiten. Die einfachste ist die Verwendung des ersten oder letzten Wertes. Es kann aber auch ein Wert aus der Mitte ausgewählt werden. Am Sichersten ist allerdings die Bildung eines Mittelwertes aus allen drei genannten Werten.
Um unser Beispiel so einfach wie möglich zu halten, setzen wir das Pivot-Element direkt auf den ersten Wert.
Wir wandern durch das Array mit zwei zusätzlichen Variablen. Mit der einen von links, dem Anfang des Arrays, beginnend, mit der anderen von rechts, dem Ende des Arrays, beginnend. Die Variable von links vergleicht jedes Element darauf, ob es nicht kleiner als das Pivot-Element ist. Sobald wir eins finden, stoppen wir. Die Variable von rechts sucht ein Element, das nicht größer als das Pivot-Element ist. Sobald wir eins gefunden haben, stoppen wir vorerst. Nun können die beiden gefundenen Elemente miteinander vertauscht werden. Nach dem Vertauschen können wir weiter fortfahren und suchen so lange nach weiteren Elementen, bis sich die beiden Variablen beim Durchlaufen des Arrays treffen oder sogar überschneiden. Unser Array ist nun dem Pivot-Element entsprechend vorsortiert.
Nun wird unser Array der Position der Variablen entsprechend "geteilt" und die Funktion erneut mit dem linken und rechten Teilarray aufgerufen. Hier beginnen wir von vorne, bestimmen ein Pivot-Element und suchen wieder von den äußeren Rändern des Teilarrays beginnend nach Werten, die im linken Teil zu groß und im rechten Teil zu klein sind. Diese werden wieder getauscht. Danach wird bei Bedarf das Array weiter geteilt und eventuell erneut rekursiv aufgerufen.
Achtung: Rekursion!
Schauen wir uns den Code dazu an. In unserem Beispiel fehlt noch das eigentliche Vertauschen der Elemente. Das könnt ihr doch sicher ergänzen, oder?
