2. Suchen und Sortieren

2.5 Quicksort

Quicksort ist vielleicht der bekannteste Sortieralgorithmus überhaupt. oberflächlich erscheint er dem Mergesort recht ähnlich zu sein; in Wirklichkeit aber gibt es zwei große Unterschiede. Erstens ist Quicksort typischerweise randomisiert, d.h., es verwendet Zufall. Zweitens ist die Laufzeitanalyse deutlich trickreicher als bei den vorherigen Algorithmen. Quicksort ist in der Praxis häufig der schnellste Sortieralgorithmus (obwohl dies auch von den genauen Umständen und der Anwendung abhängt).

Die Idee von Quicksort ist einfach. Wir nehmen ein zufälliges Element unseres Arrays array und nennen es pivot. Dann teilen wir das Array in zwei Teile auf, nämlich smaller, bestehend aus allen Elementen, die kleiner sind als Pivot, und larger (alle größeren); und ein drittes Array equal aus denjenigen Elementen, die gleich groß sind wie pivot. Wir sortieren rekursiv smaller und larger und fügen in einem letzten Schritt alles wieder zusammen: smaller + equal + larger. Die Implementierung in Python ist sehr einfach:

def quicksort(array):
    n = len(array)
    if n < 2 :
        return array
    pivot = array[0] 
    smaller = [x for x in array if x < pivot]
    equal = [x for x in array if x == pivot] # in der Praxis kann dies mehr als ein Element sein! 
    larger = [x for x in array if x > pivot]
    return quicksort(smaller) + equal + quicksort(larger)                        
                    

Um die Laufzeit von Quicksort zu verstehen, ist es essentiell, dass wir uns die Rekursionsbäume vor Augen halten. Ich zeige Ihnen nun eine Animation, die die rekursiven Aufrufe von Quicksort visualisiert:

Laufzeitanalyse

Betrachten wir noch einmal in Ruhe das Endergebnis, also den Rekursionsbaum von Quicksrt:

Wie sie in der letzten Übung gesehen haben, kann Quicksort im schlimmsten Fall tatsächlich sehr viele Vergleichsoperationen durchführen. Paradoxerweise tritt dies dann auf, wenn das Array bereits sortiert ist!

Laufzeitanalyse

Um Quicksort zu einem guten Algorithmus zu machen, müssen wir es schaffen, den Worst-Case des vollständig oder auch nur teilweise sortieren Arrays zu vermeiden. Am einfachsten geht das, indem man am Anfang das Array shuffelt, also mischt. Doch dazu später mehr. Die Laufzeitanalyse von Quicksort ist nicht offensichtlich und erfordert einige Tricks und Techniken, unter Anderem aus der Wahrscheinlichkeitsrechnung.

Der Schlüssel liegt darin, die richtige Frage zu stellen. In den unteren Rekursionsbaum wäre das zum Beispiel: Warum werden be und of nicht verglichen?

In der Tat: warum werden be und of nicht verglichen? Weil sie durch in getrennt werden! Was heißt hier "getrennt" werden? Sei $$ die Position im Array, an dem Element $$ vorkommt. Hier also $$ und $$. Wir sehen, dass

$$ und gleichzeitig $$

In Worten: in kommt im Array vor be und of, im Alphabet aber dazwischen. Und spätestens nachdem in Quicksort das Element in als Pivot drankommt, sind be und of getrennt und werden nicht mehr verglichen. Formalisieren wir das ganze nun.

Im folgenden wird es sich lohnen, den obigen Baum etwas zu verschlanken und für jeden Knoten nur das erste Element zu behalten.

Wir führen nun ein Symbol ein, das im Prinzip zählt, ob Fall 1 eingetreten ist. Für je zwei Elemente $$ definieren wir eine Indikatorvariable $$ wie folgt:

$$

Damit keine Zweideutigkeiten aufkommen: es gilt $$, weil $$ zwar nach mathematischer Konvention ein Vorfahre von sich selbst ist, aber eben kein echter Vorfahre. Wir können $$ schön als Matrix $$ darstellen. Beachten Sie aber, dass $$ von der Reihenfolge der Elemente im Array abhängt. Strenggenommen sollten wir also $$ bzw. $$ schreiben. Hier ein Beispiel mit den Elementen $$:

Um nun die Gesamtzahl der Vergleichsoperationen auszurechnen, müssen wir zählen, wie oft Fall 1 oder Fall 2 aufgetreten ist. Aber halt: wir müssen tatsächlich nur Fall 1 zählen; denn tritt Fall 2 ein (wie zum Beispiel für das Paar be, in, dann wird Fall 1 für das Paar in, be auftreten. Wenn wir also alle Paare zählen (in jeglicher Reihenfolge), dann müssen wir tatsächlich nur Fall 1 zählen. Daher:

Randomisierung

Jetzt kommt die Randomisierung ins Spiel. Wir stellen uns vor, dass wir zuerst einmal ein zufälliges Shuffling erzeugen, also die Einträge des Arrays in zufällige Reihenfolge bringen. Dann lassen wir Quicksort auf ddiesem Shuffling laufen, also

def randomizedQuicksort(array):                        
  random.shuffle(array)
  quicksort(array)

Da nun aber die Anzahl der Vergleichsoperationen vom konkreten Shuffling abhängt, dass randomizedQuicksort in Zeile 2 gewählt haben, sollten wir ($$) so schreiben:

$$

um eben die Abhängigkeit vom konkreten Shuffling hervorzuheben. Wenn wir die Laufzeit eines randomisierten Algorithmus untersuchen, dann interessiert uns normalerweise die erwartete Laufzeit, die also "im Schnitt" auftritt. Was heißt das in unserem Fall? Wir wollen ($$), gemittelt über alle Shufflings. Wie mittelt man? Indem man über alle Shufflings summiert und dann durch die Anzahl der Shufflings dividiert. Also:

$$

Wir müssen also alle möglichen Shufflings untersuchen, um den Mittelwert zu ermitteln. Das klingt enorm komplex. Hier kommt ein Trick ins Spiel, den man in der Mathematik als Linearität des Erwartungswertes bezeichnet. Wir können die Summierung in ($$) ja vertauschen, also

$$

Was ist der Vorteil? Nun ja, wir können uns nun auf zwei verschiedene Elemente $$ konzentrieren und versuchen, für dieses Paar den Wert der Klammer, also

$$

zu bestimmen. Was stellt dieser Wert denn dar? Er besagt, welchen Wert die Variable $$ annimmt, wenn wir über alle Shufflings mitteln. Wie oft im Schnitt er also 1 ist; wie oft im Schnitt also Fall 1 eintritt; wie oft im Mittel also tatsächlich $$ das Minimum fur Elemente in $$ ist; mit welcher Wahrscheinlichkeit also $$ als erstes aller Elemente aus $$ im Shuffling drankommt. (Beachten Sie hier, dass $$ nicht vom Shuffling abhängt.) Daher:

$$

Und was ist die Wahrscheinlichkeit? Wenn $$ Studierende in zufälliger Reihenfolge in eine mündliche Prüfung gerufen werden, und Sie einer Lerngruppe von $$ Studierenden davon angehören, was ist dann die Wahrscheinlichkeit, die Sie als erster oder erste aus Ihrer Lerngruppe drankommen? Ganz klar $$.

Von nun an wird es von Vorteil sein, unsere $$ Elemente als $$ durchzunumerieren. Dann können wir nämlich für $$ eine einfache Formel anbieten. Was zum Beispiel ist $$? Als Menge gilt $$, also $$. Im allgemeinen natürlich $$. Aber Vorsicht: das gilt nur, wenn $$ ist. Ansonsten ist es $$, wie zum Bespiel $$. Also:

$$

Aber das muss uns gar nicht interessieren. Denn: wenn wir die Summe ($$) betrachten, dann kommt ja jeder Wert $$ zweimal dran: einmal als $$ und einmal als $$. Wir können uns also auf die Ausdrücke beschränken, wo $$ gilt, und dann das ganze mit 2 multiplizieren:

$$

Da diese Summe immer noch etwas furchteinflößend aussieht, stellen wir sie wieder als $$-$$-Matrix dar:

Unser gewünschter Wert, die erwartete Anzahl von Vergleichsoperationen, ist also die Summe der Zahlen in dieser Matrix. Der einfachste Weg, diese nach oben abzuschätzen ist, noch ein paar fiktive Zahlen dazuzuaddieren:

Wir machen das Produkt also "teurer als nötig"; das ist aber in Ordnung, denn unser Ziel ist es ja, eine Aussage der Form "Quicksort macht im Schnitt höchstens ... Vergleiche" zu zeigen. Jede Zeile in der obigen Matrix ergibt die Summe

$$

Diese Summe hat keine "geschlossene" Form, kommt aber recht häufig vor. Daher hat man für sie das Symbol $$ und den Namen "$$-te harmonische Zahl" erfunden. Die Matrix hat insgesamt $$ Zeilen, und somit schließen wir:

Genaure Analyse

Wir haben in Theorem 1.7 eine obere Schranke hergeleitet. Bis ($$) haben wir exakt gerechnet, also keinerlei Abschätzungen vorgenommen. Könnte es also sein, dass die erwartete Anzahl von Vergleichen in Wirklichkeit deutlich geringer ist als in Theorem 1.7? (Ich verrate es Ihnen: das ist sie nicht; allerdings können wir erst dann ruhig schlafen, wenn wir uns davon überzeugt haben.) Auch dient die recht komplizierte Rechnung, die sich jetzt anschließt, dazu, Ihnen Techniken für die Summenmanipulation beizubringen. Betrachten wir noch einmal die obige Matrix, nun um eine zusätzliche Zeile erweitert:

Die erwartete Anzahl an Vergleichen ist 2 mal die Summe der schwarzen Zahlen. Die Gesamtheit der schwarzen, blauen und roten Zahlen addiert sich zu $$, da jede Zeile sich zu $$ addiert und es insgesamt $$ Zeilen sind. Um die schwarze Summe zu ermitteln, können wir nun zum Beispiel die blauen und roten Zahlen addieren und das Ergebnis dann von $$ abziehen. Die blauen Zahlen summieren sich zu $$ auf, das ist einfach. Die roten sind etwas schwieriger. Der Trick besteht darin, nicht Zeilen oder Spalten zu betrachten, sondern die Zahlen diagonal zu addieren:

Wir sehen, dass sich jede fallende Diagonale zu 1 aufaddiert. Die Summe der roten Zahlen ist also ebenfalls $$. Jetzt fügen wir alles zusammen:

$$

Schlussendlich dürfen wir nicht vergessen, die Summe der schwarzen Zahlen mit 2 zu multiplizieren:

$$

Meine Implementierung ist sehr schlampig. Sehen Sie, dass jedes Element dreimal mit dem Pivot verglichen wird, und zwar in Zeile 6, 7, und 8. Eine sauberere Implementierung könnte das mit einem Vergleich hinbekommen. Dennoch ist Quicksort selbst in dieser rudimentären Implementierung schneller als Mergesort und Heapsort. Hier sehen Sie die Laufzeiten in Sekunden für Arrays verschiedener Größe:

length of input	Mergesort	Heapsort	Quicksort
8000	0.0389379980006197	0.06752109599983669	0.02765761100090458
16000	0.07571700700100337	0.14723161900110426	0.06383249400096247
32000	0.1558326260001195	0.3184903329984081	0.12433080700066057
64000	0.3328166669998609	0.7593994590006332	0.2662465240009624
128000	0.722483514000487	1.5454070180003328	0.5753753440003493

Quickselect

Wie finde ich in einem Array das $$-kleinste Element? Ich kann natürlich das Array sortieren und dann array[k] zurückgeben. Das klingt aber nach zuviel arbeit. Der Algorithmus Quickselect ist schneller, indem er Quicksort nur dort wo nötig ausführt und andere unnötige rekursive Aufrufe sein lässt.