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.

Im linken Teilfeld befinden sich jetzt auf jeden Fall Elemente, die kleiner oder gleich dem Vergleichselement 79 sind. Im rechten sind solche, die größer oder gleich 79 sind.

Die nächsten Schritte geben wir nur noch grafisch an. Das Vergleichselement wird kursiv fett gekennzeichnet. Wir geben jeweils die Zerlegung aller Teilfelder in einer Zeile an, auch wenn es in der Praxis so ist, dass das am weitesten links gelegene Teilfeld zuerst vollständig zerlegt wird.

Hier sieht man noch folgenden Sonderfall im zweiten Teilfeld: bleiben beide Zeiger auf demselben Element stehen (das kann nur das Vergleichselement sein), kann man das Vergleichselement unmittelbar als Einser-Feld abtrennen.

Laufzeitverhalten von Quicksort:

Im Idealfall wird jedes Teilfeld wieder in der Mitte geteilt (dem kommt man besonders nahe, wenn das Vergleichselement nicht sehr groß bzw. sehr klein, eben „mittel“, war). Betrachten wir jeweils alle Teilfelder auf einer Zerlegungsstufe gemeinsam, so haben wir $n$ Vergleiche (denn jedes Element wird ja einem Vergleich unterzogen) und im Durchschnitt $\frac{1}{4}\cdot n$.Tauschoperationen (im ungünstigsten Fall $\frac{1}{2}\cdot n$ , im günstigsten Fall keine Vertauschungen). Zusammen ergibt dies $\frac{5}{4}\cdot n$ Operationen pro Zerlegungsstufe. Bei idealer Zerlegung muss für die Anzahl $k$ der Zerlegungsstufen gelten: $2^k=n$ (denn jedes Teilfeld wird ja stets halbiert), d.h. $k=\log_2(n)$ .

Also ist das Laufzeitverhalten im Idealfall:

$$k\cdot \frac{5}{4} \cdot n = \log_2(n) \cdot \frac{5}{4} \cdot n = \frac{5}{4}\cdot n \cdot \log_2(n) \sim n \cdot \log(n)$$ (da die Logarithmen zu verschiedenen Basen sich nur durch einen konstanten Faktor unterscheiden, wird keine explizite Basis mehr angegeben).

Der ungünstigste Fall entsteht, wenn jeweils nur ein 1-Teilfeld abgespaltet wird. Man erhält dann $k=n$ Zerlegungsstufen und damit $$n\cdot \frac{5}{4} \cdot n = \frac{5}{4} \cdot n^2 \sim n^2$$ Operationen, das Laufzeitverhalten des Sortierverfahrens ist dann quadratisch. Dieser ungünstigste Fall wird erreicht, wenn das Vergleichselement jeweils das größte oder kleinste Element im Teilfeld ist.

Sortiere den Notenspiegel mit Quicksort.

2 Sortiere das Feld

mit Quicksort

Sortiere das Zahlenfeld

mit Quicksort

Überlege, ob das Vergleichselement eines der Feldelemente sein muss.

Es gibt eine Verbesserung von Quicksort, bei der man als Kandidaten für das Vergleichselement das ganz links, das ganz rechts und das in der Mitte in Erwägung zieht. Welches sollte man nehmen? Wann bringt diese Abänderung Vorteile?