\documentstyle[A4,11pt,german]{article} \begin{document} \begin{center} \Large Quicksort \end{center} \normalsize \section{Vorbemerkung} Der um 1960 von {\sc C.A.R. Hoare} vorgeschlagene Sortieralgorithmus {\em quicksort} geh"ort zweifellos zu den popul"arsten, am meisten verwendeten und am besten untersuchten Algorithmen "uberhaupt. Sortieren ist ohnehin eine recht h"aufige Aufgabe, und mit einigem Recht kann man {\em quicksort} als einen der besten ``general-purpose'' Sortieralgorithmen ansprechen. Solche Qualifizierungen bed"urfen nat"urlich einer genaueren Begr"undung, die ihrerseits nur auf der Basis umfangreicher Erfahrung und Vergleiche m"oglich ist. Dar"uber ist soviel und kompetent geschrieben worden, da"s es keinen Sinn macht, das hier in wenigen S"atzen darstellen zu wollen. Ein Verweis auf Autorit"aten wie {\sc Knuth}, {\sc Sedgewick} und {\sc Bentley} mu"s gen"ugen. Insbesondere die Dissertation von {\em Sedgewick} ist ein studierenswertes Beispiel skrupul"oser Auseinandersetzung mit Implementierung und Analyse der algorithmischen Idee von {\em quicksort}. So bestechend einfach die urspr"ungliche Idee von {\em Hoare} ist, ihre Realsierung ist durchaus nicht ohne T"ucken! Die Zeigerbewegungen in der {\em splitting}-Phase mu"s man sehr sorgf"altig behandeln, spezielle Vorkehrungen sind zu treffen, um das {\em worst-case} Verhalten\footnote{das sich bei naiver Implementierung paradoxerweise gerade dann zeigt, wenn man {\em quicksort} auf schon weitgehend sortierte Listen anwendet} zu verbessern, und durch iterative Implementierung kann man zwar die Effizienz steigen, die Programmierung wird aber delikater. Die Analyse des {\em average-case} Verhaltens von {\em quicksort} ist ein ``Klassiker'' der Algorithmenanalyse, und darum geht es hier vor allem. Wie schon in den fr"uher behandelten {\em divide-and-conquer} Situationen f"uhrt die rekursive Struktur des Algorithmus auf eine Rekursionsgleichung f"ur die Kosten. Hier allerdings kann die Problemgr"osse der jeweils induzierten Teilprobleme stark schwanken --- was sich in einem anderen Typ von Rekursionsgleichung "aussert. Es wird sich zeigen, da"s {\em quicksort} im Mittel einen Aufwand (gemessen in der Anzahl der Vergleichsoperationen) ben"otigt, der sich bei Listenl"ange $n$ wie $2 n\,\log n$ verh"alt, also asymptotisch von optimaler Wachstumsordnung ist. Dies korrespondiert mit den guten praktischen Erfahrungen, die ja auch noch den overhead des Verfahrens ber"ucksichtigen, der bei der Z"ahlung der Vergleichsoperationen unterschlagen wird. {\em quicksort} kann aus dieser Sicht sehr gut mit Algorithmen wie {\em heapsort} oder {\em mergesort} konkurrieren, die ja auch im {\em worst case} ein $\Theta(n \,\log n)$ verhalten zeigen. \section{Die Idee --- rekursives splitting} {\em quicksort} basiert auf einer bestechend einfachen Idee (man mu"s nur darauf kommen): \begin{quote} In einer zu sortierenden Liste $A[1..n]$ (von ganzen Zahlen etwa) ist das Element an der $k$-ten Position, $A[k]$ also, ein {\em splitter}, wenn es an der ``richtigen'' Position in Bezug auf die Liste steht, die aus $A[1..n]$ durch Sortieren entsteht. D.h. es gilt \[ \forall i < k ~:~A[i] \leq A[k]~~\wedge~~ \forall j > k ~:~A[k] \leq A[j] \] Hat man eine solche Information, kann man $A[1..n]$ dadurch sortieren, da"s man die Teillisten $A[1..k-1]$ und $A[k+1..n]$ separat sortiert. Hat man eine solche Information nicht, wird man durch eine spezielle Prozedur {\em split} (mit m"oglichst wenig Aufwand) $A[1..n]$ so umordnen, da"s dabei ein {\em splitter} in einer bekannten Position (!) entsteht --- dann kann man zu den Teillisten wie beschrieben "ubergehen und dieses Verfahren rekursiv anwenden. \end{quote} Eine {\em quicksort}-Implementierung hat also die Struktur \begin{verbatim} qksort := proc(A:array(integer),left:integer,right:integer) if left < right then split(A,left,right,'k'); qksort(A,left,k-1); qksort(A,k+1,right) fi; end; \end{verbatim} wobei der Aufruf zum Sortieren von {\tt A[left..right]} so behandelt wird, da"s durch den Aufruf {\tt split(A,left,right,'k')} eine Umordnung {\tt A'[left..right]} von {\tt A[left..right]} ({\em in place}) erzeugt wird, bei der {\tt A'[k]} ein {\em splitter} ist. Auf {\tt A'[left..k-1]} und {\tt A'[k+1..right]} wird das Verfahren rekursiv angewandt. Der ganze Witz von {\em quicksort} liegt also im {\em splitting}~! \section{Splitting} Die urspr"ungliche Idee von {\sc Hoare} besteht darin, zum Splitten einer Liste $A[1..n]$ so vorzugehen, da"s man zwei Zeiger, $i$ und $j$, und zwar $i$ von 1 her aufsteigend, $j$ von $n$ her absteigend, aufeinander zubewegt. Jedesmal, wenn man $A[i] > A[j]$ feststellt, werden diese beiden Elemente vertauscht --- danach setzen die Zeiger ihren Weg analog fort. Treffen sich die beiden Zeiger, hat man die Position eines {\em splitters} gefunden. Die Details der Zeigerbewegungen (Randf"alle!) sind etwas subtil. Man kann sie in der Literatur nachlesen. Konzeptuell und f"ur die Implementierung etwas einfacher ist eine elegante Idee von {\sc N. Lomuto}, die von {\sc Bentley} propagiert wird. Hier bewegen sich auch zwei Zeiger $i$ und $j$, aber in der gleichen Richtung! Das Listenelement $A[1]$ soll {\em splitter} werden. Man startet mit $j$ von $j=1$ aus und l"auft so lange, bis man einen Index $j$ mit $A[j] < A[1]$ findet - dann erh"oht man $i$ (das auch bei $i=1$ startet) um 1 und vertauscht $A[i]$ und $A[j]$. Dieses Spiel ($j$ erh"ohen bis wieder $A[j] < A[1]$ gefunden wird, dann mit $i$ um eine Stelle nachziehen und $A[i]$ mit $A[j]$ vertauschen) setzt sich fort, bis Zeiger $j$ das Listenende erreicht. Dann werden $A[i]$ und $A[1]$ vertauscht --- mit dem Erfolg, da"s das nunmehr an der Stelle $i$ stehende Element (das anf"angliche A[1]) ein {\em splitter} der Liste ist. Es geht kein Weg dran vorbei: wenn man verstehen will, wie und warum das funktioniert, mu"s man sich --- etwa anhand des weiter unten reproduzierten Programmtextes --- Schritt f"ur Schritt durch Beispiele arbeiten. Das bleibt der Eigeninitiative "uberlassen. Vorher aber noch ein Hinweis auf eine sinnvolle Modifikation der Splittings. \section{Eine Verbesserung: Splitting mit ``Randomisieren''} Die eben beschriebene Idee des Splittings hat noch einen Nachteil: es gibt (sehr einfache!) Listen, bei denen die Aufteilung in Teillisten vor und nach dem {\em splitter} sehr extrem ausf"allt, wenn man das erste Listenelement als Vergleichselement nimmt: die linke Teilliste ist leer und die L"ange der rechten Teilliste ist gerade mal um 1 kleiner als die L"ange des urspr"unglichen inputs. Wenn sich diese Erscheinung durch alle Phasen des Algorithmus durchzieht, wird er ein {\em quadratisches} Laufzeitverhalten im {\em worst case} haben! "Argerlich daran ist, da"s dieses ``schlechte'' Verhalten immer bei denselben inputs auftritt. Was man zumindest erreichen m"ochte, ist dies: es gibt keine inputs bei denen sich der Algorithmus {\em immer} schlecht verh"alt. Das kann man bei einem seiner Natur nach {\em deterministischen} Algorithmus nur dadurch erreichen, indem man ein {\em zuf"alliges} Element mit einbaut. Wenn man das geschickt macht, kann man daf"ur sorgen, da"s es keine {\em schlechten Instanzen} f"ur den Algorithmus gibt, sondern nur noch {\em schlechte Exekutionen}. Beim Splitting kann man eine solche Verbesserung dadurch erreichen, da"s man zu Beginn ein zuf"alliges Element $A[r]$ mit $1 \leq r \leq n$ ausw"ahlt und mit $A[1]$ vertauscht. Damit haben alle Listenelemente die gleiche Chance, {\em splitter} zu sein, unabh"angig von der urspr"unglichen Form der Liste. Klar ist dann auch, da"s die {\em Position} $k$ des {\em splitters} jede der Positionen $1 \leq k \leq n$ mit gleicher Wahrscheinlichkeit $1/n$ sein wird. Die hier angesprochene Technik des ``Randomisierens'' ist in den letzten Jahren sehr popul"ar geworden. ``Randomisierte Algorithmen'', auch f"ur Problemstellungen, wo man ein determiniertes Resultat erwartet, k"onnen u.a. verhindern, da"s lange Laufzeiten immer bei den gleichen inputs auftreten (wenn sie denn unvermeidbar sind). F"ur viele Fragestellungen gibt es randomisierte Algorithmen, die weitaus besser sind als die besten deterministischen Algorithmen, wenn man noch geringe ``Versagerquoten'' in Kauf zu nehmen bereit ist. \section{Das Programm} In diesem Abschnitt wird ein {\sc Maple} Programm {\em quicksort} pr"asentiert. Dabei kommt es nur auf die korrekte und klare Realisierung der dargestellten Ideen an, nicht auf Effizienzsteigerung durch Detailverbesserung. Interessenten (insbesondere auch solche, die sich mit den Interna von {\sc Maple} etwas auskennen), sind eingeladen, dieses Programm zu ``tunen'' oder gleich eine noch Maschinen-n"aheres Programm zu schreiben. Es wurde ebenfalls darauf verzichtet, Konsistenz-checks der Eingabedaten mit in die einzelnen Prozeduren aufzunehmen. Die Prozedur {\tt swap} dient lediglich dazu, zwei Elemente eines arrays zu vertauschen, n"amlich die Elemente in Position {\tt u} und Position {\tt v}. \begin{verbatim} swap := proc(A:array(integer),u:integer,v:integer) local tmp; if not (u=v) then tmp := A[u]; A[u] := A[v]; A[v] := tmp; fi; RETURN(op(A)); end; \end{verbatim} Die Prozedur {\tt split} ist das Herzst"uck von {\em quicksort}. Hierbei wird der Abschnitt {\tt A[left..right]} eines arrays {\tt A[lower..upper]} dem {\em splitting} unterworfen --- es wird unterstellt, da"s {\tt left} und {\tt right} mit den array-Grenzen vertr"aglich sind. Aus dem Intervall {\tt [left..right]} wird per Zufallsgenerator ein {\tt r} ausgew"ahlt, und {\tt A[r]} wird als {\em splitting}-Element bestimmt (und mit {\tt A[left]} vertauscht). Der Index {\tt I} als Resultat der Prozedur gibt an, in welcher Position dieses Element {\em nach} dem {\em splitting} steht. Als Seiteneffekt wird {\tt A} entsprechend dem {\em splitting} ver"andert. \newpage \begin{verbatim} split := proc(A:array(integer),left:integer,right:integer,I:string) local i,j,r; r := rand(left..right)(); swap(A,left,r); i := left; for j from left+1 to right do if A[j] < A[left] then i := i+1; swap(A,i,j) fi; od; swap(A,left,i); I:=i; end; \end{verbatim} Die rekursive Struktur von {\em quicksort} wurde schon oben angesprochen. {\tt qksort} sortiert den Bereich {\tt A[left..right]} der arrays {\tt A}, indem durch {\tt split(A,left,right,'k')} ein {\em splitter} an der Stelle {\tt k} erzeugt wird. F"ur Teilarrays links und rechts davon wird {\tt qksort} rekursiv aufgerufen. Bei arrays der L"ange $\leq 1$ ist nichts zu tun.\footnote{ Bei ``richtigen'' Implementierungen von {\em quicksort} wird man die Rekursion nicht so weit treiben: man schaltet auf ein schnelles, nichtrekursives Verfahren (wie z.B. {\em insertionsort} um, sobald die L"ange der arrays 10-15 (etwa) unterschreitet.} \begin{verbatim} qksort := proc(A:array(integer),left:integer,right:integer) local k; if left < right then split(A,left,right,'k'); qksort(A,left,k-1); qksort(A,k+1,right) fi; end; \end{verbatim} {\tt quicksort(L)} schlie"slich sortiert Listen {\tt L} durch Aufruf von {\tt qksort} mit der Listenl"ange als Parameter. \begin{verbatim} quicksort := proc(L:list(integer)) local length,A; length := nops(L); A := convert(L,array); qksort(A,1,length); convert(op(A),list); end \end{verbatim} \section{Die {\em quicksort}-Rekursion} Es bezeichne nun $F(n)$ die {\em mittlere Anzahl} von Vergleichsoperationen, bei Ausf"uhrung von {\em quicksort} auf Listen der L"ange $n$. Wie schon fr"uher wollen wir annehmen, da"s alle $n!$ relativen Anordnungen (Permutationen) von $n$ Elementen mit der gleichen Wahrscheinlichkeit auftreten. Aus der Struktur des Algorithmus ergibt sich somit: \[ F(n) = (n-1) + {1 \over n} \sum_{k=1}^n \left\{ F(k-1)+F(n-k) \right\} \] wobei $n-1$ die Anzahl der Vergleichsoperationen in {\em split} bei Listenl"ange $n$ ist, und $k$ die Position des {\em splitters} angibt: jede dieser Positionen hat die gleiche Wahrscheinlichkeit $1/n$. Zu Sortieren sind dann Teillisten der L"angen $k-1$ und $n-k$, und man "uberlegt sich leicht, da"s hierbei wiederum alle $(k-1)!$ bzw $(n-k)!$ relativen Anordnungen mit gleicher Wahrscheinlichkeit auftreten. Eine kleine Vereinfachung ergibt sich aus der Beobachtung, da"s auf der rechten Seite der Rekursion zweimal die gleiche Summe (mit unterschiedlicher Summationsrichtung) steht, also: \[ F(0) = 0~,~F(n) = n-1+{2 \over n} \sum_{i=0}^{n-1} F(i) \] Die Frage ist nun, wie sich die L"osung $F(n)$ dieser Rekursion f"ur $n \rightarrow \infty$ verh"alt. Experimentell wird rasch klar, da"s $F(n)$ st"arker als linear w"achst, aber auch nicht sehr viel st"arker: \begin{eqnarray*} F(1) &=& 0 \\ F(2) &=& 1 \\ F(3) &=& 8/3 = 2.66... \\ F(4) &=& 29/6 = 4.83... \\ F(5) &=& 37/5 = 7.4 \\ F(6) &=& 10.3 \\ F(7) &=& 13.48... \\ F(8) &=& 16.92... \\ F(9) &=& 20.57... \\ F(10) &=& 30791/1260 = 24.43... \\ F(100) &=& 647.85... \\ F(1000) &=& 10985.9... \end{eqnarray*} Interessant ist, da"s sich die L"osung der {\em quicksort}-Rekursion {\em explizit} angeben l"a"st: \[ F(n) = 2 \,(n+1)\,H_n - 4\,n \] und damit kann man leicht auch den Funktionsverlauf f"ur gr"o"sere $n$ verfolgen: \begin{eqnarray*} F(10^4) &=& 155771.6... \\ F(10^5) &=& 0.2018...\,10^7 \\ F(10^6) &=& 0.2478... \,10^8 \\ F(10^7) &=& 0.2939... \, 10^9 \\ F(10^8) &=& 0.3399... \, 10^{10} \\ F(10^9) &=& 0.3860... \, 10^{11} \\ F(10^{10}) &=& 0.4320... \, 10^{12} \end{eqnarray*} Insgesamt zeigt sich also: \[ F(n) \sim 2\, n \, \log n \] \section{Zur Analyse der Quicksort-Rekursion} In einem ersten Abschnitt wird die Quicksort-Rekursion behandelt, indem sie in eine Differenzengleichung umgeformt wird, die einer expliziten L"osung zug"anglich ist. Allgemeiner gilt, da"s sich Rekursionen dieses Typs mit Hilfe von Differentialgleichungen f"ur die ``erzeugenden Funktionen'' der L"osung beschreiben lassen. Diese Technik wird in einem zweiten Abschnitt vorgestellt. \subsection{Behandlung mittels Differenzengleichung} Wir schreiben die Quicksort-Rekursion \[ F(0) = 0~,~F(n) = n-1+{2 \over n} \sum_{i=0}^{n-1} F(i) \] in der Form \[ n \, F(n) =n(n-1) + 2 \sum_{i=1}^{n} F(i-1)~~~(n > 0) \] und ziehen diese Gleichung, aber mit $n$ durch $n-1$ ersetzt, also \[ (n-1) \, F(n-1) = (n-1)(n-2) + 2 \sum_{i=1}^{n-1} F(i-1)~~~(n > 0) \] von der vorigen Gleichung ab: \[ n \, F(n) - (n-1) \, F(n-1) = 2\,(n-1) + 2 \, F(n-1) \] Das ergibt \[ n \, F(n) - (n+1) \, F(n-1) = 2\,(n-1) \] Dies ist eine lineare Differenzengleichung 1. Ordnung mit {\em polynomialen} Koeffizienten. Ersetzt man $F(n)$ durch $(n+1) \,G(n)$, so gen"ugt diese neue Funktion $G(n)$ einer linearen Differenzengleichung 1. Ordnung mit {\em konstanten} Koeffizienten: \[ G(n) - G(n-1) = {2\,(n-1) \over n\,(n+1)}~~(n>0)~,~~G(0)=0 \] Hier kann man zweimal den ``Teleskop-Trick'' spielen: \begin{eqnarray*} G(n) &=& \sum_{i=1}^n \left\{ G(i) - G(i-1) \right\} \\ &=& \sum_{i=1}^n {2\,(i-1) \over i\,(i+1) } \\ &=& 2 \,\sum_{i=1}^n \left\{ {2 \over i+1} - {1 \over i} \right\} \\ &=& 2 \,\sum_{i=1}^n \left\{ {2 \over i+1} - {2 \over i} \right\}+ 2 \,\sum_{i=1}^n {1 \over i} \\ &=& 2 \,\left\{ {2 \over n+1} - 2 \right\} + 2 \,H_n \\ &=& -{4\,n \over n+1} + 2\, H_n \end{eqnarray*} und somit \[ F(n) = (n+1)\,G(n) = 2\,(n+1)\,H_n -4\,n \sim 2\,n \, \log n \] \subsection{Behandlung mittels Differentialgleichung} Wir betrachten wieder \[ F(0) = 0~,~F(n) = n-1+{2 \over n} \sum_{i=0}^{n-1} F(i) \] und definieren uns die ``erzeugende Funktion'' \[ \phi(z) := \sum_{n \geq 0} F(n) \, z^n \] Multiplikation der Rekursionsgleichung mit $n$ liefert \[ n \, F(n) =n(n-1) + 2 \sum_{i=0}^{n-1} F(i)~~~(n \geq 0) \] Multiplikation mit $z^n$ und Summation "uber $n \geq 0$ ergibt \[ \sum_{n \geq 1} n \, F(n) \, z^n =\sum_{n \geq 1}n(n-1) \,z^n + 2 \sum_{n \geq 1}\sum_{i=0}^{n-1} F(i)\,z^n \] und das ist "aquivalent zu \[ \phi'(z) ={2z \over (1-z)^3} + {2 \over 1-z}\,\phi(z) \] Diese lineare Differentialgleichung kann man mittels der Methode der {\em Variation der Konstanten} l"osen. Dazu betrachtet man erst einmal die zugeh"orige {\em homogene} Gleichung \[ \phi_h'(z) = {2 \over 1-z}\, \phi_h(z) \] die man leicht l"osen kann. \[ {d \over dz} \, \log \phi_h(z) ={ \phi_h'(z) \over \phi_h(z) } ={2 \over 1-z} \] liefert \[ \log \phi_h(z) = -2 \log(1-z) + \gamma \] mit einer Integrationskonstanten $\gamma$, also \[ \phi_h(z) = { \lambda \over (1-z)^2} \] mit einer Konstanten $\lambda$. Nun der Ansatz \[ \phi(z) = {\lambda(z) \over (1-z)^2} \] d.h. f"ur die Behandlung der inhomogenen Gleichung wird $\phi(z)$ so angesetzt, da"s an Stelle der Konstanten $\lambda$ eine Funktion $\lambda(z)$ erscheint. Dies in die ursp"ungliche Differentialgleichung eingesetzt liefert eine Differentialgleichung f"ur die zu bestimmende Funktion $\lambda(z)$: \[ {\lambda'(z) \over (1-z)^2} = {2z \over (1-z)^3} \] oder \[ \lambda'(z) ={2z \over 1-z} = {2 \over 1-z} -2 \] was offenbar durch \[ \lambda(z) = 2\,( - \log(1-z) - z) + c \] gel"ost wird. Hierbei ist $c$ eine passende Konstante. Damit hat man die L"osung: \[ \phi(z) = 2 \left({-1 \over (1-z)^2} \log(1-z) - {z \over (1-z)^2} \right) + c \] Davon interessiert uns die Potenzreihenentwicklung. Es gilt \begin{eqnarray*} {-1 \over (1-z)^2} \log(1-z) &=&\sum_{i \geq 0} (i+1)\,z^i \cdot\sum_{j > 0} {z^j \over j} \\ &=&\sum_{n > 0}\left(\sum_{j=1}^n (n-j+1)\, {1 \over j} \right)\, z^n \\ &=&\sum_{n>0}\left( (n+1)H_n - n \right)\, z^n \end{eqnarray*} und daher kann man schreiben: \[ \phi(z) = \sum_{n \geq 0} F(n)\,z^n = 2 \left( \sum_{n>0}\left( (n+1)\, H_n -n\right) \,z^n - \sum_{n > 0} n \, z^n \right) + c \] was per Koeffizientenvergleich zu \[ \Rightarrow F(n) = 2\,(n+1) H_n - 4\,n~~~(n>0) \] f"uhrt. \section{Empfohlene Literatur} \begin{enumerate} \item C.A.R. Hoare, Quicksort, \newline {\em Computer Journal} 5 (1962), 10-15. \item R. Sedgewick, {\em Quicksort}, \newline ACM Outstanding Dissertations in Computer Science (Stanford, 1975), \newline Garland, 1980. \newline 14GI/mat 8.7-50[492 \item R. Sedgewick, Implementing quicksort programs, \newline {\em Communications of the ACM} 21 (1978), 847-857. \item R. Sedgewick, Quicksort, \newline Kapitel 9 in {\em Algorithms}. \item Cormen/Leiserson/Rivest, Quicksort, \newline Kapitel 8. in {\em Introduction to Algorithms}. \item J. Bentley, Kolumne 10 in {\em Communications of the ACM}, 27 (1984). \newline ist abgedruckt in: \item J. Bentley, {\em Programming Pearls}, \newline Addison-Wesley, 1986/89. \newline 14GI/mat 12.2-83 \end{enumerate} \end{document}