Ü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: $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Aber seine durchschnittliche Laufzeit ist so gut wie die von Mergesort: $\Theta(n \log_2 n)$\Theta, left parenthesis, n, log, start base, 2, end base, n, right parenthesis.

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.

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 Elemente, die also größer als Pivot sind, 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.

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. Nach der Partitionierung erhalten wir [7, 9, 10] links vom Pivot und [14, 12] rechts vom Pivot. Dann werden diese Subarrays sortiert, wir erhalten [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:

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.