Quicksort

Prinzip: Das Feld wird in zwei Teilfelder zerlegt, wobei im linken Teilfeld nur Elemente stehen, die kleiner oder gleich einem Vergleichselement sind, im rechten nur solche, die größer oder gleich sind. Das Verfahren wird mit den Teilfeldern solange fortgesetzt, bis nur noch Teilfelder mit einem Element vorhanden sind.

Bei Quicksort wird über größere Entfernungen getauscht. Zu Beginn wird ein Zähler auf den linken Rand des zu sortierenden Teilfeldes gesetzt, ein zweiter Zähler auf den rechten Rand. Als Ver¬gleichselement wird das mittig gelegene Element des Teilfeldes genommen (bzw. das links von der Mitte, wenn die Zahl der Elemente gerade ist).

Die Zähler wandern nun nacheinander, der linke Zähler nach rechts, bis er auf ein Element stößt, das größer oder gleich dem Vergleichs¬element ist, der rechte nach links, bis er ein Element kleiner oder gleich dem Vergleichselement findet (das „gleich“ ist deshalb wichtig, damit die Zähler mit Sicherheit noch im Feld stoppen). Diese beiden Elemente werden getauscht und die Zähler wandern weiter, bis sie auf ein neues Paar stoßen, usw.

Die Sache wird gestoppt, wenn die Zähler aneinander vorbeilaufen. Hier erfolgt eine Aufspaltung des Feldes und beide Teilfelder werden einzeln wieder von Quicksort bearbeitet.

Beispiel:

Vergleichselement ist 79. Der linke Zeiger stoppt bei 95, der rechte Zeiger sofort bei 2. Es wird getauscht. Der linke Zeiger macht einen Schritt nach rechts, der rechte nach links und der Vergleich beginnt erneut. Stopp Links bei 79 (der Fall „gleich“), Stopp Rechts bei 66, Tausch. Jeweils einen Schritt weiter. Stopp Links bei 92, Stopp Rechts bei 67, Tausch und jeweils einen Schritt weiter. Jetzt haben sich die Zeiger gekreuzt und hier wird das Feld in zwei Teilfelder geteilt.