Sortierverfahren
Quicksort
by Dr. M. Halfpap
Zurück zur Hauptseite
Quicksort (sprachliche Formulierung)
Die vorgegebene Liste der zu sortierenden Daten wird unter Verwendung eines beliebigen
Elements als Grenze in zwei Teillisten zerlegt. Die linke Teilliste enthält nur Elemente, die nicht
größer als das kleinste Element der rechten Teilliste sind. (Als Grenze wird oft der linke Rand der
Liste benutzt.)
Man gewinnt die beiden Teillisten, indem man von links und von rechts so weit in die Liste
hineingeht, bis man jeweils zu einem Element kommt, daß nicht in diese Teilliste hineingehört.
Diese beiden Elemente werden dann miteinander vertauscht.
Dann geht das Durchsuchen von links und rechts weiter, bis man sich überschneidet. Damit ist die
Grenze zwischen der linken und der rechten Teilliste gefunden.
Auf die beiden Teillisten wird das gleiche Verfahren solange erneut angewendet, bis die jeweiligen
Teillisten die Länge 1 haben; es handelt sich somit um einen rekursiven Algorithmus.
