Quicksort
erfahrungsgemäß eine der schnellsten Methoden
Divide and Conquer-Verfahren:
- Zerlege die Folge F= a[1],...,a[n] in zwei Folgen F1 und F2, so daß gilt:
Für jeden Schlüsselwert ki1 der Folge F1 und jeden Schlüsselwert ki2 der Folge F2 gilt die Beziehung ki1 < ki2 ,
d. h. jedes Element der ersten Teilfolge ist kleiner als jedes Element der zweiten Teilfolge.
- Führe diese Zerlegung wiederum für beide Folgen F1 und F2 durch, usw.
- Das Verfahren bricht für eine Teilfolge ab, wenn diese einelementig ist.
Nach dem Abbruch des Verfahrens ist dann die gesamte Folge sortiert. Wir beschreiben den Vorgang des Zerlegens und Zusammensetzens etwas genauer: