Page in English Page in English

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:

  1. Falls die Reihung weniger als zwei Elemente enthält, sind wir bereits fertig.
  2. Man nimmt ein (beliebiges) Element p aus der Reihung R heraus.
  3. Dann partitioniert man die Reihung in zwei Teilreihungen R1 und R2:
    R1 = {x in R | x<p} und R2 = {x in R | x>=p}
  4. Jedes Element in R2 ist größer als das größte Element in R1. 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:

Verweise zu Quicksort:



zurück zur Startseite

Valid XHTML 1.0!