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:

Beobachtung Jede Vergleichsoperation in Quicksort findet statt zwischen dem rot markierten Pivot-Element und den anderen Elementen in diesem Knoten.

Übungsaufgabe Zeichnen Sie den Rekursionsbaum für Quicksort auf dem Array [4,2,6,1,5,7,3] und zählen die Anzahl der ausgeführten Vergleichsoperationen. Wiederholen Sie die Übung für [1,2,3,4,5,6,7]

Übungsaufgabe Wie viele Vergleichsoperationen führt Quicksort auf dem Array $[1,2,\dots,n]$ aus?

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!

Beobachtung Im Worst-Case macht Quicksort ${n \choose 2} = \frac{n(n-1)}{2}$ Vergleichsoperationen, also genau so viele wie Selectionsort.

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 $\pos(x)$ die Position im Array, an dem Element $x$ vorkommt. Hier also $\pos(\texttt{of}) = 1$ und $\pos(\texttt{in}) = 0$. Wir sehen, dass

\begin{align*} \texttt{be} \lt \texttt{in} \lt \texttt{of} \end{align*} und gleichzeitig \begin{align*} \pos(\texttt{in}) \lt \pos(\texttt{be}) \textnormal{ und } \pos(\texttt{in}) \lt \pos(\texttt{of}) \ . \end{align*}

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.

Definition Für Elemente $x,y$ aus dem Array bezeichnen wir mit $[x:y]$ die Menge der Elemente, die dazwischen liegen, also

\begin{align*} [x:y] := \{z \in \textnormal{Array} \ | \ x \le z \le y \textnormal{ or } y \le z \le x \} \ . \end{align*}

Beispielsweise gilt für obiges Array $[\texttt{of}:\texttt{be}] = \{\texttt{in}, \texttt{of}, \texttt{it}, \texttt{is}, \texttt{be}\}$ und $[\texttt{as}: \texttt{in}] = \{\texttt{as}, \texttt{be}, \texttt{in}\}$

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

Lemma Seien $x,y$ zwei verschiedene Elemente aus dem Array. Sei $z \in [x:y]$ das Element, das im Array als erstes drankommt, also das mit minimalen $\pos(z)$ von allen Elementen aus $[x:y]$.

Falls $z = x$, also $x$ als allererstes kommt, dann vergleicht Quicksort $x$ mit $y$, und zwar zu dem Zeitpunkt, wo $x$ als Pivot ausgewählt wird; im Quicksortbaum ist $x$ ein Vorfahre von $y$. Beispiel: $x = \texttt{of}, y = \texttt{is}$.
Falls $z = y$, also $z$ als allererstes kommt, dann vergleicht Quicksort $x$ mit $y$, und zwar zu dem Zeitpunkt, wo $y$ als Pivot ausgewählt wird; im Quicksortbaum ist $y$ ein Vorfahre von $x$. Beispiel: $x = \texttt{be}, y = \texttt{in}$.
Falls $z$ weder $x$ noch $y$ ist, also ein ganz anderes Element $z$ die kleinste Position $\pos(z)$ aller Elemente in $[x:y]$ hat, dann werden $x$ und $y$ nicht verglichen; im Quicksort-Baum sind $x$ und $y$ Nachfahren von $z$, sie werden also zu dem Zeitpunkt in verschiedene Teilarrays gesteckt, wo $z$ als Pivot ausgewählt wird.

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

\begin{align} I_{x,y} := \begin{cases} 1 & \textnormal{ wenn $x$ ein echter Vorfahre von $y$ im Quicksortbaum ist} \\ 0 & \textnormal{ sonst.} \end{cases} \label{def-Ixy} \end{align}

Damit keine Zweideutigkeiten aufkommen: es gilt $I_{x,x} = 0$, weil $x$ zwar nach mathematischer Konvention ein Vorfahre von sich selbst ist, aber eben kein echter Vorfahre. Wir können $I_{x,y}$ schön als Matrix $I$ darstellen. Beachten Sie aber, dass $I$ von der Reihenfolge der Elemente im Array abhängt. Strenggenommen sollten wir also $I({\rm array})$ bzw. $I_{x,y}({\rm array})$ schreiben. Hier ein Beispiel mit den Elementen $\{a,b,c,d,e,f,g\}$:

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:

Lemma Die Gesamtzahl an Vergleichsoperationen, die Quicksort auf einem Array ausführt, ist

\begin{align} \sum_{x \in \texttt{array}} \ \sum_{y \in \texttt{array}} I_{x,y} \label{quicksort-total-comparisons} \end{align}

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 (\ref{quicksort-total-comparisons}) so schreiben:

\begin{align} \sum_{x \in \texttt{array}} \ \sum_{y \in \texttt{array}} I_{x,y} ({\rm shuffling}) \ , \label{quicksort-total-comparisons-2} \end{align}

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 (\ref{quicksort-total-comparisons-2}), gemittelt über alle Shufflings. Wie mittelt man? Indem man über alle Shufflings summiert und dann durch die Anzahl der Shufflings dividiert. Also:

\begin{align} \frac{1}{\textnormal{Anzahl der Shufflings}} \sum_{\rm shufflings} \sum_{x \in \texttt{array}} \ \sum_{y \in \texttt{array}} I_{x,y} ({\rm shuffling}) \label{total-3} \end{align}

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 (\ref{total-3}) ja vertauschen, also

\begin{align*} \sum_{x \in \texttt{array}} \ \sum_{y \in \texttt{array}} \left( \frac{1}{\textnormal{Anzahl der Shufflings}} \sum_{\rm shufflings} I_{x,y} ({\rm shuffling}) \right) \end{align*}

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

\begin{align} \frac{1}{\textnormal{Anzahl der Shufflings}} \sum_{\rm shufflings} I_{x,y} ({\rm shuffling}) \label{total-4} \end{align}

zu bestimmen. Was stellt dieser Wert denn dar? Er besagt, welchen Wert die Variable $I_{x,y}$ 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 $\pos(x)$ das Minimum fur Elemente in $[x:y]$ ist; mit welcher Wahrscheinlichkeit also $x$ als erstes aller Elemente aus $[x:y]$ im Shuffling drankommt. (Beachten Sie hier, dass $[x:]$ nicht vom Shuffling abhängt.) Daher:

\begin{align*} (\ref{total-4}) = \Pr[x \textnormal{ kommt im Shuffling als erstes aller Elemente aus $[x:y]$ dran}] \end{align*}

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

Lemma Es gilt

\begin{align*} \Pr[x \textnormal{ kommt im Shuffling als erstes aller Elemente aus $[x:y]$ dran}] = \frac{1}{|[x:y]|} \end{align*}

und somit ist die erwartete Anzahl an Vergleichsoperationen gleich

\begin{align} \sum_{x \in {\rm array}} \sum_{y \in{\rm array}, x \ne y} \frac{1}{|[x:y]|} \ . \label{total-5} \end{align}

Von nun an wird es von Vorteil sein, unsere $n$ Elemente als $1, \dots, n$ durchzunumerieren. Dann können wir nämlich für $|[x:y]|$ eine einfache Formel anbieten. Was zum Beispiel ist $|[8:11]|$? Als Menge gilt $[8:11] = \{8,9,10,11\}$, also $|[8:11]| = 4$. Im allgemeinen natürlich $|[x:y]| = y - x + 1$. Aber Vorsicht: das gilt nur, wenn $x \leq y$ ist. Ansonsten ist es $x - y + 1$, wie zum Bespiel $|[7:5]| = |\{5,6,7\}| = 3$. Also:

\begin{align*} |[x:y]| = |x - y| + 1 \ . \end{align*}

Aber das muss uns gar nicht interessieren. Denn: wenn wir die Summe (\ref{total-5}) betrachten, dann kommt ja jeder Wert $|[x:y]|$ zweimal dran: einmal als $|[x:y]|$ und einmal als $|[y:x]|$. Wir können uns also auf die Ausdrücke beschränken, wo $y \gt x$ gilt, und dann das ganze mit 2 multiplizieren:

\begin{align} (\ref{total-5}) = 2 \cdot \sum_{x=1}^n \sum_{y = x+1}^n \frac{1}{y-x+1} \ . \label{runtime-as-sum} \end{align}

Da diese Summe immer noch etwas furchteinflößend aussieht, stellen wir sie wieder als $x$-$y$-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

\begin{align*} 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{n} =: H_n \ . \end{align*}

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

Theorem Auf einem Array der Länge $n$ tätigt quicksortRandomized im Erwartungswert höchstens

\begin{align*} n H_n \end{align*}

Vergleiche. Der Ausdruck $H_n := 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$ ist die $n$-te harmonische Zahl.

Genaure Analyse

Wir haben in Theorem 1.7 eine obere Schranke hergeleitet. Bis (\ref{runtime-as-sum}) 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 $(n+1) H_n$, da jede Zeile sich zu $H_n$ addiert und es insgesamt $n+1$ 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 $nH_n$ abziehen. Die blauen Zahlen summieren sich zu $n$ 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 $n$. Jetzt fügen wir alles zusammen:

\begin{align*} \textnormal{Summe der schwarzen Zahlen} & = (\textnormal{Summe aller Zahlen}) - (\textcolor{blue}{\textnormal{blaue Zahlen}}) - (\textcolor{red}{\textnormal{rote Zahlen}})\\ & = (n+1) H_n - n - n \\ & = n H_n + H_n - 2n \ . \end{align*}

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

\begin{align*} \textnormal{Erwartete Anzahl an Vergleichen} & = 2 \times (\textnormal{schwarze Zahlen}) \\ & = 2 n H_n - 4n + 2H_n \ . \end{align*}

Theorem Auf einem Array der Länge $n$ tätigt quicksortRandomized im Erwartungswert exakt $2 n H_n - 4n + 2H_n$ Vergleiche.

Bis hier.

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

Übungsaufgabe

Zeigen Sie, wie man Quicksort in place implementiert. Schreiben Sie hierfür Code (Pseudo-Code, Python, was auch immer) für eine Funktion splitByPivot (array, pivotIndex, leftIndex, rightIndex), der folgendes leistet:

Schreiben Sie dann eine Funktion quicksortInPlace, die eben keine neuen Arrays anlegt, sondern sich mit verschiedenen Indices (leftIndex, rightIndex) auf dem Eingabe-Array aufruft und splitByPivot als Subroutine verwendet.

Übungsaufgabe

Lesen Sie meine Notizen zu Quicksort und führen Sie die Laufzeitanalyse zu Ende!

Wägen Sie für sich selbst ab, wie genau Sie rechnen wollen und wie bequem Sie rechnen wollen. Erinnern Sie sich an Mergesort: die Anzahl der Operationen, um die sortierten Hälften von array per merge zusammenzufügen, war im Worstcase $n-1$. Ich hatte in der Vorlesung aber mit $n$ weitergerechnet; aus Bequemlichkeit.

Quickselect

Wie finde ich in einem Array das $k$-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.

Übungsaufgabe

Machen Sie sich mit der Idee und dem Code von QuickSelect vertraut. Lesen Sie hierzu die letzten paar Seiten meiner Notizen zu Quicksort. Der Bequemlichkeit halber hier nochmal mein Python-Code für Quickselect:

def quickselect(array,k):
	n = len(array)
	if (n <= 1):
		return array[0]
	pivot = array[0]	
	left = [x for x in array if x < pivot]
	same = [x for x in array if x == pivot]
	right= [x for x in array if x > pivot]

	if (k < len(left)):		
		return quickselect(left,k)
	elif (k >= len(left) + len(same)):		
		return quickselect(right, k - len(left) - len(same))
	else:		
		return pivot

Den Code finden Sie zusammen mit allen anderen Sortieralgorithm auch unter sorting.py.

Führen Sie per Hand quickselect(array,2) aus für array = ['b','i','f','g','a','j','e','d','h','c']. Erinnern Sie sich an den Quicksort-Baum für array:

Malen Sie diesen Baum ab und demonstrieren, dass man quickselect(array,2) als ein nur teilweise ausgeführtes quicksort(array) betrachten kann. Zeigen Sie, welche Teile des Baumes von quickselect(array,2) besucht/erzeugt/erschlossen werden und welche ignoriert werden.

Übungsaufgabe

Erinnern Sie sich an die Indikatorvariable $A_{xy}$, die in quicksort-quickselect.pdf definiert wird. Sie ist 1 falls $x$ ein Vorfahre von $y$ ist (ansonsten ist sie 0). Wir haben gesehen, dass $A_{xy}$ auch genau dann 1 ist, wenn Quicksort zu dem Zeitpunkt, wo $x$ als Pivot gewählt wird, es mit $y$ vergleicht.

Ich will eine entsprechende Variable $B_{kxy}$ definieren, die uns das gleiche für Quickselect anzeigt: dass die Ausführung von Quickselect irgendwann $x$ mit $y$ vergleicht, wobei $x$ als Pivot ausgewählt ist. Beachten Sie, dass $B_{kxy}$ auch von dem gesuchten Rang $k$ abhängt.

Zeigen Sie, wie man ein solches $B_{kxy}$ mit Hilfe des Quicksort-Baumes definieren kann. Das heißt, zeigen Sie, wie Sie den Wert von $B_{kxy}$ bestimmen kann, wenn man nur den Quicksort-Baum vom array sieht, nicht aber array selbst (sehen Sie: Sie können array nicht vollständig rekonstruieren, wenn Sie nur seinen Quicksort/Baum sehen).

Übungsaufgabe

quicksort-quickselect.pdf haben wir gesehen, dass $A_{xy}$ genau dann 1 ist, wenn $x$ von allen Elementen im Interval $[x:y]$ als erstes in array vorkommt. Finden Sie eine ähnliche Charakterisierung für $B_{kxy}$.

Übungsaufgabe

Schreiben Sie die erwartete Anzahl von Vergleichsoperationen, die quickselect(array,k) macht, als Summe und versuchen, deren Wert zu bestimmen. Wiederum müssen Sie zwischen Genauigkeit und vertretbarem Arbeitsaufwand Ihrerseits abwägen.