Quicksort

Quicksort wurde 1962 von C.A.R. Hoare erfunden. Er erweist sich in der Praxis als der schnellste Sortieralgorithmus.

Legende:
rosa: grösserer Vergleichspartner
rot: kleinerer Vergleichspartner
gelb: Pivot-Element
orange: bereits sortiertes Teil-Array
blau: Animation aktiv

Die Idee ist wie folgt:

Falls die Reihung weniger als zwei Elemente enthält, sind wir bereits fertig.
Man nimmt ein (beliebiges) Element p aus der Reihung R heraus.
Dann partitioniert man die Reihung in zwei Teilreihungen R₁ und R₂:
R₁ = {x in R | x<p} und R₂ = {x in R | x>=p}
Jedes Element in R₂ ist größer als das größte Element in R₁. Die beiden Teilreihungen können jetzt unabhängig voneinander sortiert werden. Man geht also für beide wieder zu Schritt 1.

Bei der Implementierung ist es wichtig, dass die Partitionierung schnell von statten geht. Ein wichtiger Punkt ist auch die Wahl des Pivot-Elementes p. Bei uns wird der Einfachheit halber für p immer das rechte Element genommen. Am schnellsten läuft Quicksort, wenn der Aufrufbaum möglichst balanciert ist. Die Laufzeit in (O-Notation) ist dann O(n log n). Im schlechtesten Fall einer bereits sortierten Reihe ist der Aufrufbaum unbalanciert, und die Laufzeit wird quadratisch. Würde für p stattdessen immer ein zufälliges Element ausgewählt, so wäre die erwartete Laufzeit bei beliebiger Eingabe wieder O(n log n).

Literatur:

C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962)

Verweise zu Quicksort:

zurück zur Startseite