Überblick über Quicksort

Genauso wie Mergesort, verwendet Quicksort eine Teile und Herrsche Strategie, ist also ein rekursiver Algorithmus. Quicksort verwendet die teile und herrsche Strategie etwas anders als Mergesort. Bei Mergesort spielt der Teile-Schritt nur eine untergeordnete Rolle und der größte Teil der Arbeit findet im Kombinations-Schritt statt. Quicksort ist das genaue Gegenteil: die eigentliche Arbeit geschieht im Teile-Schritt wohingegen im Kombinations-Schritt rein gar nichts passiert.
Quicksort unterscheidet sich von Mergesort in ein paar Punkten. Quicksort arbeitet an Ort und Stelle. Und seine Laufzeit ist selbst im ungünstigsten Fall wie die von Selektionsort und Insertionsort: Θ(n2) \Theta(n^2) . Aber seine durchschnittliche Laufzeit ist so gut wie die von Mergesort: Θ(nlgn) \Theta(n \lg n) . Warum sollte man sich deshalb mit Quicksort befassen, wenn Mergesort zumindest ebensogut ist? Der Grund dafür ist, dass der konstante Faktor, der in der big-Θ Notation für Quicksort versteckt ist, ganz gut ist. In der Praxis übertrifft Quicksort Mergesort und übertrifft die Selektion-Sort und Insertion-Sort deutlich.
Quicksort verwendet die teile und herrsche Strategie wie folgt: Wie bei Mergesort, sortieren wir ein Subarray array[p..r], wobei das anfängliche Subarray array[0..n-1] ist.
  1. Teile durch Auswahl eines beliebigen Elements im Subarray array[p..r]. Wir nennen dieses Element das Pivot . Ordne die Elemente in array[p..r] so an, dass alle Elemente in array[p..r], die kleiner oder gleich dem Pivot sind, links vom Pivot liegen, und alle anderen Elemente (die also größer als Pivot sind) in array [p. .r] recht des Pivots liegen. Wir nennen dieses Verfahren Partitionierung . An dieser Stelle spielt es keine Rolle, in welcher Ordnung die Elemente zueinander stehen. Es genügt, dass Elemente kleiner gleich Pivot links und Elemente größer als Pivot rechts sind.
    Aus praktischen Gründen wählen wir stets das am weitesten Rechts stehende Element im Subarray array[r] als Pivot. Wenn also das Subarray aus den Zahlen [9, 7, 5, 11, 12, 2, 14, 3, 10, 6] besteht, dann wählen wir 6 als Pivot. Nach der Partitionierung könnte das Subarray wie folgt aussehen: [5, 2, 3, 6, 12, 7, 14, 9, 10, 11]. Wir definieren q als Index und setzen diesen auf die Position des Pivot im Subarray.
  2. Herrsche durch rekursive Sortierung der Subarrays array[p..q-1] (alle Elemente links vom Pivot, die kleiner oder gleich dem Pivot sein müssen) und array[q + 1..r](alle Elemente rechts vom Pivot, die größer als Pivot sein müssen).
  3. Kombiniere, indem wir nichts tun. Sobald der Herrsche-Schritt rekursiv sortiert hat, sind wir fertig. Warum? Alle Elemente links vom Pivot, in array[p..q-1], sind kleiner oder gleich dem Pivot und werden sortiert, und alle Elemente rechts vom Pivot, in array[q + 1..r], sind größer als das Pivot und sind auch sortiert. Die Elemente in array[p..r] können also nicht umhin, auch sortiert zu sein!
    Wenden wir uns wieder unserem Beispiel zu. Nach der rekursiven Sortierung der Subarrays links und rechts vom Pivot enthält das Subarray links vom Pivot die Zahlenfolge [2, 3, 5] und das Subarray rechts vom Pivot die Zahlenfolge [7, 9, 10, 11, 12, 14]. So enthält das gesamte Subarray erst [2, 3, 5], gefolgt von 6 (unserem Pivot), gefolgt von [7, 9, 10, 11, 12, 14]. Das Subarray ist also komplett sortiert.
Die Basis-Fälle sind Subarrays mit weniger als zwei Elementen, genau wie bei Mergesort. Dort kommt nie ein Subarray ohne Elemente vor, aber diese kann bei Quicksort passieren und zwar dann, wenn alle anderen Elemente im Subarray entweder alle kleiner oder alle größer als Pivot sind.
Schauen wir uns nochmal den Herrsche-Schritt (2) an und arbeiten uns durch die rekursive Sortierung der Subarrays. Nach der ersten Partitionierung haben wir die beiden Subarrays [5, 2, 3] und [12, 7, 14, 9, 10, 11], mit 6 als Pivot.
Um das Subarray [5, 2, 3] zu sortieren, wählen wir 3 als Pivot. Nach der Partitionierung erhalten wir [2, 3, 5]. Das Subarray [2], links vom Pivot, ist ein Grundfall, weil es aus weniger als 2 Elementen besteht, ebenso wie das Subarray [5], rechts vom Pivot.
Um das Subarray [12, 7, 14, 9, 10, 11] zu sortieren, wählen wir 11 als Pivot, was zu [7, 9, 10] links vom Pivot und [14, 12] rechts vom Pivot führt. Nachdem diese Subarrays sortiert sind, haben wir [7, 9, 10], gefolgt von 11, gefolgt von [12, 14].
Die folgende Abbildung veranschaulicht die Anwendung des Quicksort Algorithmus auf unser Beilspielarray. Blaue Felder waren in vorherigen rekursiven Anrufen Pivots, und deswegen werden die Werte an diesen Feldern nicht weiter untersucht oder erneut verschoben:
Quicksort

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.