Quicksort
Alle drei Sortierverfahren der Einführungsphase brauchen im schlechtesten Fall quadratischen Aufwand. Bei einer Million Datensätzen wären das 500 Milliarden Vergleiche – Tage an Rechenzeit.
Mit Teilen und Herrschen geht es sehr viel besser.
Die Idee
Quicksort wählt ein Element als Pivot (Angelpunkt) und ordnet das Feld so um, dass links vom Pivot nur kleinere und rechts nur größere Werte stehen. Damit steht das Pivot bereits an seiner endgültigen Stelle.
Danach sortiert das Verfahren die beiden Teilbereiche rekursiv nach demselben Muster.
Das Umordnen heißt Partitionieren und ist der Kern des Verfahrens.
Mit Karten
Legt euch die Karten 5 2 8 1 9 3 7 hin.
- Nehmt die letzte Karte als Pivot – hier die 7.
- Geht die übrigen von links nach rechts durch. Alles, was kleiner als 7 ist, legt ihr nach links; alles Größere bleibt rechts.
- Legt das Pivot zwischen die beiden Gruppen.
Wie sieht das Feld danach aus? An welcher Stelle steht die 7?
Auflösung
Kleiner als 7: 5 2 1 3. Größer: 8 9.
Ergebnis: 5 2 1 3 | 7 | 8 9
Die 7 steht jetzt an Index 4 – und dort bleibt sie für immer. Alles links davon ist kleiner, alles rechts größer.
Jetzt macht man dasselbe noch einmal mit 5 2 1 3 und mit 8 9.
Das Verfahren
a) Verfolge die Ausgabe. In welcher Reihenfolge kommen die Pivots an ihren Platz?
b) Was bewirkt die Variable grenze in partitioniere? Formuliere in einem Satz, was zu jedem Zeitpunkt links von ihr steht.
c) Warum steht am Ende von partitioniere noch ein Tausch?
Auflösung
a) Zuerst das Pivot des ganzen Feldes, dann die Pivots der linken Hälfte, dann die der rechten. Das Verfahren arbeitet den linken Ast vollständig ab, bevor es zum rechten kommt – wie jede Rekursion.
b) grenze markiert die Stelle, an der der nächste kleine Wert hingehört. Links von ihr stehen zu jedem Zeitpunkt alle bisher gefundenen Werte, die kleiner als das Pivot sind.
c) Das Pivot liegt bis dahin noch ganz rechts. Der letzte Tausch bringt es genau an die Grenze – also zwischen die Kleineren und die Größeren.
Wie schnell ist Quicksort?
a) Angenommen, das Pivot teilt den Bereich immer genau in der Mitte. Wie oft kann man ein Feld mit 1000 Elementen halbieren?
b) Jede Partitionierungsebene betrachtet zusammen alle n Elemente. Wie viele Vergleiche ergibt das insgesamt?
c) Was passiert, wenn das Pivot immer das kleinste Element des Bereichs ist? Wann tritt dieser Fall bei unserer Pivotwahl ein?
Auflösung
a) Etwa 10 Mal – dasselbe Argument wie bei der binären Suche.
b) Auf jeder Ebene werden zusammen n Elemente betrachtet, und es gibt etwa log n Ebenen. Also n · log n Vergleiche.
Bei einer Million Elementen: 1 000 000 · 20 = 20 Millionen statt 500 Milliarden. Das ist ein Faktor 25 000.
c) Dann liegen alle übrigen Elemente auf einer Seite, und der Bereich schrumpft nur um eins. Das ergibt n Ebenen statt log n – der Aufwand wird wieder quadratisch.
Bei unserer Pivotwahl (immer das letzte Element) tritt das genau dann ein, wenn das Feld bereits sortiert ist. Das ist eine unangenehme Eigenschaft: Ausgerechnet der schönste Fall ist der schlimmste.
| Vergleiche | |
|---|---|
| bester und mittlerer Fall | n · log n |
| schlechtester Fall | n² / 2 |
In der Praxis ist Quicksort trotzdem eines der schnellsten Verfahren. Der schlechteste Fall lässt sich fast vollständig vermeiden, indem man das Pivot geschickter wählt – etwa den mittleren von drei Werten, oder einen zufälligen.
Aufgabe 1: Selbst implementieren
Ergänze die Methoden so, dass alle Tests grün werden.
Tipp 1: partitioniere
int pivot = pWerte[pRechts];
int grenze = pLinks;
for (int i = pLinks; i < pRechts; i++) {
if (pWerte[i] < pivot) {
tausche(pWerte, i, grenze);
grenze++;
}
}
tausche(pWerte, grenze, pRechts);
return grenze;Beachte, dass die Schleife bei pRechts aufhört – das Pivot selbst wird nicht mitgeprüft.
Tipp 2: sortiere
Drei Zeilen:
if (pLinks >= pRechts) {
return;
}
int teiler = partitioniere(pWerte, pLinks, pRechts);
sortiere(pWerte, pLinks, teiler - 1);
sortiere(pWerte, teiler + 1, pRechts);Der Basisfall ist ein Bereich mit höchstens einem Element – der ist schon sortiert.
Tipp 3: Warum teiler minus 1 und teiler plus 1?
Weil das Pivot an Index teiler bereits endgültig richtig steht. Es darf nicht noch einmal mitsortiert werden – sonst schrumpfen die Bereiche nicht und die Rekursion endet nie.
Aufgabe 2: Der schlechteste Fall
Miss, wie viele Vergleiche Quicksort bei verschiedenen Ausgangslagen braucht.
a) Zufällige Werte
b) Bereits aufsteigend sortiert
c) Absteigend sortiert
Erkläre die Unterschiede. Bei welcher Ausgangslage tritt der schlechteste Fall ein, und warum?
Auflösung
Typische Werte bei n = 2000:
| Ausgangslage | Vergleiche | Größenordnung |
|---|---|---|
| zufällig | etwa 25 000 | n · log n |
| aufsteigend | etwa 2 000 000 | n² / 2 |
| absteigend | etwa 2 000 000 | n² / 2 |
Bei einem sortierten Feld ist das letzte Element immer das größte. Das Pivot landet also stets ganz rechts, der linke Teilbereich enthält alles übrige, und der Bereich schrumpft nur um eins pro Ebene.
Bei einem absteigend sortierten Feld passiert dasselbe spiegelverkehrt.
Beides sind in der Praxis häufige Fälle – Daten liegen oft schon teilweise sortiert vor. Deshalb wählt kein ernsthaftes Programm das letzte Element als Pivot.
Verbessere die Pivotwahl: Nimm statt des letzten Elements den mittleren von dreien – dem ersten, dem mittleren und dem letzten Element des Bereichs. Tausche ihn ans Ende und partitioniere wie gehabt.
Miss danach noch einmal alle drei Ausgangslagen. Was hat sich geändert?
Zusatzaufgabe
Visualisiere Quicksort mit Scratch for Java:
- Stelle die Werte als Säulen dar.
- Färbe während der Partitionierung das Pivot rot, den bereits abgearbeiteten Bereich blau und den noch offenen grau.
- Zeichne nach jedem abgeschlossenen Partitionierungsschritt neu und pausiere kurz.
Vergleiche die Animation mit der von Bubblesort aus der Einführungsphase. Woran sieht man den Unterschied im Aufwand?