2.5 Quicksort

Quicksort wurde 1960 von Tony Hoare (C.A.R. Hoare) erfunden und ist der schnellste bekannte Sortieralgorithmus. Bei ungünstiger Sortierung der Daten hat er allerdings ein schlechtes Laufzeitverhalten. Mit einigen Verbesserungen zeigt er aber, daß bessere Algorithmen schneller als ausgefeilte Programme sind. Da Quicksort recht trickreich ist, besteht die Gefahr, bei einer Implementierung Fehler bei den Indexwerten einzubauen. Quicksort läßt sich rekursiv wie folgt beschreiben:

1. Nimm einen Wert aus dem Feld
2. Suche eine Position in dem Feld, so daß alle kleineren Elemente als der Wert aus Punkt 1 in das Teilfeld vor diese Position und alle größeren in das Teilfeld hinter diese Position passen.
3. Verschiebe alle Elemente, die kleiner als das in Punkt 1 gefundene sind, in das Teilfeld vor der in Punkt 2 gefundenen Position.
4. Verschiebe alle Elemente, die größer als das in Punkt 1 gefundene sind, in das Teilfeld hinter der in Punkt 2 gefundenen Position.
5. wende die Schritte 1 - 4 auf die beiden Teilfelder an.

Die Kunst besteht nun darin, ein geeignetes Element für die Aufteilung des Feldes in zwei Teilfelder zu finden. Eine mögliche Aufteilung des Feldes kann wie folgt durchgeführt werden:

1. Nim das letzte Element
2. Suche von vorn solange, bis ein Element gefunden wurde, das größer als das gemerkte ist.
3. Suche von hinten solange, bis ein Element gefunden wurde, das kleiner als das gemerkte ist.
4. vertausche die beiden gefundenen Elemente
5. führe die Schritte 2 - 3 solange durch, bis sich die Suche von vorn und von hinten überkreuzt.
6. Setze das in Schritt 1 gefundenen Element an diese Position ein.

Dazu ein Beipiel mit folgenden unsortierten Feld:

Wir merken uns das letzte Element 3 und fangen vorn mit der 5 und hinten mit der 4 an. Da 5 größer als 3 ist, haben wir von vorn das zu vertauschende Element gefunden. 4 ist größer als 3, also gehen wir von hinten ein Element weiter. 2 ist kleiner als 3, wir vertauschen 5 und 2.

Wenn wir jetzt weitersuchen, würde das nächste Element von vorn und das nächste Element von hinten die 1 sein, wir können also das Vertauschen beenden und müssen nur noch die 3 einsetzen. Da 3 größer als die 1 (und auch alle davor stehenden Element) ist, aber kleiner als dio 5, wird es mit der 5 vertauscht.

Jetzt müssen nur noch die beiden Teilfelder sortiert werden:

und

Zusätzlich zu dem rekursiven Beispiel gibt es noch eine iterative Lösung, die die Rekursion mit Hilfe eines Stack auflöst. Das dritte Beispiel benutzt für kürzere Teillisten Insertsort.

English version not yet available.