Die eigentliche Magie von Quicksort geschieht in der partition-Funktion. Grob gesagt passiert hier folgendes: zuerst wird in Zeile (8) und (9) durch die Funktion choose ein Pivot-Element ausgewählt (siehe dazu unten); im Anschluss wird in Zeile (10) das Pivot-Element vorübergehend ans rechte Ende des Feldes geschoben. In den Zeilen (12) bis (15) wird durch das Feld von links nach rechts iteriert (mit Ausnahme des Pivot-Elements ganz rechts) und der in Zeile (11) initialisierte Index immer dann erhöht, wenn im Feld ein Element kleiner als das Pivot-Element gefunden wird; der Index markiert dabei die Stelle im Feld, bis zu der alle Elemente kleiner als das Pivot sind. Durch die Vertauschung in Zeile (14) wird sichergestellt, dass alle Element links des Indexes diese Bedingung erfüllen. Im Anschluss wird in Zeile (16) das temporär nach rechts geschobene Pivot-Element an die Stelle des Indexes kopiert, so dass die eben genannte Bedingung tatsächlich gilt und alle Elemente links des Pivot-Elements kleiner als das Element selber sind; schließlich wird in Zeile (17) der bestimmte Index zur weiteren Verwendung zurückgegeben.
Ein kleines Beispiel zur Verdeutlichung; nehmen wir an, wir haben das folgende (Teil-)Feld zum Sortieren:
Durch die Funktion choose wird nun zum Beispiel die 4 als Pivot-Element gewählt (markiert durch ein kleines p):
p
Als erstes wird das Pivot nun ganz nach rechts gesetzt, so dass sich folgendes Bild ergibt:
p
Nun beginnt der eigentliche Algorithmus; das Feld wird von links nach rechts durchlaufen (markiert durch die Laufvariable i), wobei der Index (markiert durch ^) immer dann verschoben wird, wenn ein Element kleiner als das Pivot-Element angetroffen wird; gleichzeitig wird in einem solchen Fall das gefundene Element mit dem Element an der Index-Position vertauscht wird (zu sehen in der 5. Zeile):
î p
î p
î p
^ i p
^ i/p
Als Endzustand ergibt sich also das folgende Umsortierte Feld, in welchem alle Elemente links des Pivot-Elements kleiner, alle rechts davon größer als das Pivot-Element selber sind. Die zurückgegebene Index-Position entspricht hier der Position der 4:
^
Nun würde man den Quicksort-Algorithmus rekursiv auf das linke und rechte Teilfeld anwenden (wobei beim rechten Teilfeld, bestehend aus der 5, keine weitere Sortierung nötig ist) und so Stück für Stück das gesamte Feld sortieren. Die Wahl des Pivot-Indexes kann übrigens nach unterschiedlichen Kriterien erfolgen; so kann zum Beispiel immer das Element ganz links oder rechts im Feld gewählt werden (wenngleich sich diese Wahl als ungünstig herausgestellt hat), es kann ein zufälliges Element gewählt werden oder ein Element, von dem erwartet werden kann, dass es ungefähr in der Mitte des Feldes zum Liegen kommt – letzteres wäre die beste Wahl für einen möglichst effizienten Algorithmus.
Die hier beschriebene Umsetzung des Quicksort-Algorithmus ist übrigens nur eine von vielen Varianten; die Bestimmung der Index-Position mit den dazu nötigen Vertauschungen kann auf unterschiedlichste Art und Weise erfolgen. In jedem Fall ist der Algorithmus aber sehr effizient und wird heutzutage als Standard-Sortieralgorithmus in vielen Programmen eingesetzt.
Und noch eine abschließende Information: Quicksort ist in der hier vorgestellten Implementierung ein sogenannter in-place-Algorithmus; derartige Algorithmen führen den Hauptteil ihrer Operationen auf den Eingabedaten selbst durch, benötigen also keinen zusätzlichen Speicherplatz zur Abarbeitung. Demgegenüber stehen die out-of-place-Algorithmen, welche folgerichtig zusätzlichen Speicherplatz benötigen (für die Interessierten: von Quicksort existiert auch eine out-of-place-Variante, welche mit Hilfe von Listen umgesetzt werden kann).
Kommentare (8)