Quicksort

Einführung

Ein in der Praxis oft eingesetzter und sehr effizienter Sortieralgorithmus ist der Quicksort (englisch für „schnelles Sortieren“). Er funktioniert nach dem Prinzip „Teile und herrsche“ (Divide and Conquer), welches in der Programmierung meist mithilfe von Rekursion realisiert wird.

Die Grundidee ist einfach: Die zu sortierende Datenmenge wird in zwei kleinere Teillisten zerlegt ("Teile") und diese werden anschließend separat sortiert ("Herrsche"). Diese Teillisten werden wiederum in noch kleinere Teillisten zerlegt, bis eine Liste nur noch aus einem einzigen Element besteht. Eine Liste mit nur einem Element ist naturgemäß immer sortiert – an diesem Punkt endet die Rekursion (vgl. Galileo Computing).

Wie funktioniert die Zerlegung (Partitionierung)?

Die Zerlegung der Liste erfolgt anhand eines sogenannten Pivot-Elements (Dreh- und Angelpunkt).

Ein beliebiges Element der Liste wird als Pivot ausgewählt.
Alle anderen Elemente der Liste werden mit diesem Pivot verglichen.
Die Liste wird in zwei Bereiche unterteilt:
- Linke Teilliste: Alle Elemente, die kleiner (oder gleich) dem Pivot sind.
- Rechte Teilliste: Alle Elemente, die größer als das Pivot sind.

Nach diesem Schritt steht das Pivot-Element bereits an seiner endgültigen, korrekten Position in der Liste. Die Elemente in der linken und rechten Teilliste sind zwar untereinander noch unsortiert, aber es ist garantiert, dass alle Elemente links vom Pivot kleiner sind als alle Elemente rechts davon.

Anschließend ruft sich der Quicksort-Algorithmus selbst auf (Rekursion), um die linke und die rechte Teilliste nach exakt demselben Muster weiter zu sortieren. Ein großer Vorteil dieses Verfahrens: Die Teillisten sind immer Abschnitte der ursprünglichen Liste. Es wird also (abgesehen vom Speicher für die Rekursionsaufrufe) kein zusätzlicher Speicherplatz für neue Listen benötigt (In-Place-Sortierung).

Beispiel

Als Beispiel betrachten wir eine unsortierte Liste mit Zahlen. Der Einfachheit halber wählen wir in diesem Beispiel immer das erste Element als Pivot-Element. Zu Beginn ist die Zahl 7 also unser Pivot.

7 10 8 6 11 4 9 3 1 5 2 12

Die Zahlen, die kleiner als das Pivot-Element 7 sind, wurden blau markiert. Die Zahlen, die größer als 7 sind, wurden rot markiert. Nach dem ersten Partitionierungsschritt hat QuickSort die Liste folgendermaßen umgeordnet:

3 2 5 6 1 4 7 9 11 8 10 12

Nun stehen alle Zahlen, die kleiner sind als 7, links von ihr. Alle Zahlen, die größer sind, stehen rechts. Die Reihenfolge der Zahlen innerhalb der blauen und roten Teillisten ist hier noch willkürlich und hängt von der genauen Programmierung ab. Entscheidend ist: Die 7 hat nun ihre endgültige, korrekte Position gefunden.

Als Nächstes wird die linke (blaue) Teilliste per QuickSort sortiert. Als neues Pivot wählen wir wieder die erste Zahl des Bereichs, die 3. Die Zahlen, die kleiner sind als 3, werden wieder blau markiert, die größeren rot. Die bereits einsortierte 7 und die rechte Teilliste ignorieren wir für den Moment (grau hinterlegt):

3 2 5 6 1 4 7 9 11 8 10 12

Der Algorithmus sortiert die Elemente relativ zur 3 um:

1 2 3 6 5 4 7 9 11 8 10 12

Dieser Prozess wird fortgesetzt (erst die 1 und 2, dann die 6, 5 und 4), bis der gesamte linke Teil des Arrays vollständig sortiert ist. Das Ergebnis sieht dann so aus:

1 2 3 4 5 6 7 9 11 8 10 12

Anschließend wird die Teilliste rechts von der 7 nach demselben Prinzip sortiert. Wieder wird ein Pivot gewählt (hier die 9), und die kleineren und größeren Zahlen werden auf die jeweils richtige Seite gebracht, bis das gesamte Array sortiert ist.

Pseudocode

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus. Bei jedem Aufruf von quicksort(...) gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1.

funktion quicksort(links, rechts) 
    falls links < rechts dann 
        // teile() ordnet das Array um und liefert die finale Position des Pivots
        teiler := teile(links, rechts) 
        
        // Rekursiver Aufruf für die linke Teilliste
        quicksort(links, teiler - 1) 
        
        // Rekursiver Aufruf für die rechte Teilliste
        quicksort(teiler + 1, rechts) 
    ende
ende

Wahl des Pivot-Elements

Die Effizienz von Quicksort steht und fällt mit der Wahl des Pivot-Elements.

Schlechteste Wahl: Das Pivot-Element ist zufällig immer das kleinste oder größte Element der Teilliste. Dann wird die Liste extrem ungleichmäßig geteilt (eine Liste mit 0 Elementen, eine mit [math]\displaystyle{ n-1 }[/math] Elementen).
Beste Wahl: Das Pivot-Element ist genau der Median (der Wert, der exakt in der Mitte der sortierten Liste stehen würde). Die Liste wird in zwei exakt gleich große Hälften geteilt. Da der Median in unsortierten Daten aber aufwendig zu suchen ist, behilft man sich mit Tricks.

Warum das erste Element oft eine schlechte Wahl ist: Wenn man immer stur das erste Element als Pivot wählt (wie in unserem Beispiel) und die Eingabeliste ist bereits (oder fast) fertig sortiert, trifft automatisch immer der oben beschriebene schlechteste Fall ein. Der Algorithmus wird dadurch extrem langsam.

Lösungsansätze für die Praxis:

Randomisierung: Man wählt ein zufälliges Element aus dem Intervall als Pivot.
Median-of-Three: Man betrachtet das erste, das mittlere und das letzte Element der Teilliste und wählt von diesen dreien den mittleren Wert als Pivot. Dies schützt sehr gut vor bereits vorsortierten Listen.

Java Implementierung

Bisher wurde die allgemeine Funktionsweise beschrieben. Am besten lassen sich komplexe Algorithmen nachvollziehen, wenn man sie anhand einer Implementierung mit Hilfe eines Debuggers analysiert. In der folgenden Java-Implementierung wird ein Array aus Ganzzahlen (int) sortiert.

Zur Abwechslung wird in dieser Implementierung immer das letzte Element des aktuellen Bereichs (array[rechts]) als Pivot gewählt.

public void quickSort(int array[], int links, int rechts) {
      if (links < rechts) {
         // Teile das Array und finde die Position des Pivot-Elements
         int i = teile(array, links, rechts);
         
         // Sortiere den linken Teil
         quickSort(array, links, i - 1);
         // Sortiere den rechten Teil
         quickSort(array, i + 1, rechts);
      }
}

public int teile(int array[], int links, int rechts) {
      int pivot, i, j, help;
      pivot = array[rechts]; // Wir wählen das rechte Randelement als Pivot               
      i = links;
      j = rechts - 1;
      
      // Von links und rechts zur Mitte laufen, bis sich i und j kreuzen
      while (i <= j) {
         // Suche von links ein Element, das größer als das Pivot ist
         if (array[i] > pivot) {     
            // Tausche array[i] mit array[j], um es in den rechten Bereich zu bringen
            help = array[i]; 
            array[i] = array[j]; 
            array[j] = help;                             
            j--; // j einen Schritt weiter nach links schieben
         } else {
            i++; // i war kleiner/gleich Pivot, ist also korrekt positioniert -> weiter nach rechts
         }          
      }

      // Das Pivot-Element an seine endgültige Position (i) tauschen
      help = array[i];
      array[i] = array[rechts];
      array[rechts] = help;
      
      // Rückgabe der finalen Position des Pivot-Elements
      return i;
}

Vorbereitung: Indikatorvariablen und die Harmonische Reihe

Bei komplexeren Algorithmen wie Quicksort reicht einfaches Zählen der Vergleiche oft nicht mehr aus. Hier arbeiten wir in der Laufzeitanalyse mit einem stochastischen Werkzeug: Indikatorvariablen und der Harmonischen Reihe. Um das Prinzip zu verinnerlichen, analysieren wir vorab einen simplen Code zur Maximumsuche:

public int findMax(int[] A) {
    int max = A[0];
    for (int i = 1; i < A.length; i++) {
        if (A[i] > max) {
            max = A[i]; // Update-Operation
        }
    }
    return max;
}

Die Vergleiche in der if-Bedingung werden immer exakt [math]\displaystyle{ n-1 }[/math] Mal ausgeführt. Aber wie oft wird die Variable max im Durchschnitt tatsächlich überschrieben (Update-Operation)?

Wir stellen uns vor, das Array enthält völlig zufällig gemischte Zahlen.

Intuitiver Ansatz:

Das 1. Element ist automatisch das bisherige Maximum (Wahrscheinlichkeit: 1). Damit das 2. Element ein neues Maximum ist, muss es größer als das erste sein. Die Chance dafür ist bei zufälliger Verteilung exakt 50% ([math]\displaystyle{ \frac{1}{2} }[/math]). Damit das 3. Element ein neues Maximum ist, muss es das Größte der ersten drei Elemente sein. Die Chance dafür ist [math]\displaystyle{ \frac{1}{3} }[/math].

Mathematischer Ansatz (Indikatorvariablen):

Wir definieren einen „Schalter“ (die Indikatorvariable) [math]\displaystyle{ X_i }[/math]. Er ist [math]\displaystyle{ 1 }[/math], wenn ein neues Maximum an Stelle [math]\displaystyle{ i }[/math] gefunden wird, sonst [math]\displaystyle{ 0 }[/math]. Die Wahrscheinlichkeit dafür ist [math]\displaystyle{ P(X_i = 1) = \frac{1}{i} }[/math].

Um die durchschnittliche Gesamtzahl der Updates zu finden, addieren wir einfach diese Wahrscheinlichkeiten auf:

[math]\displaystyle{ E[X] = \sum_{i=1}^{n} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{n} }[/math]

Diese spezielle Summe nennt man in der Mathematik die Harmonische Reihe ([math]\displaystyle{ H_n }[/math]). Sie wächst extrem langsam. Für große Zahlen [math]\displaystyle{ n }[/math] entspricht sie in etwa dem natürlichen Logarithmus ([math]\displaystyle{ \ln(n) }[/math]).

Erkenntnis für Quicksort: Obwohl das Array [math]\displaystyle{ n }[/math] Elemente hat, wird die Update-Operation im Durchschnitt nur logarithmisch oft ([math]\displaystyle{ \mathcal{O}(\log n) }[/math]) ausgeführt. Genau dieses stochastische Prinzip (das Aufsummieren von Einzelwahrscheinlichkeiten, die zu einem Logarithmus führen) ist der Schlüssel, um im nächsten Abschnitt zu beweisen, dass Quicksort im Average-Case bei [math]\displaystyle{ \mathcal{O}(n \log n) }[/math] liegt.

Laufzeitanalyse

Best-Case (Bester Fall)

Der beste Fall liegt vor, wenn das Pivot-Element die Liste in jedem Rekursionsschritt exakt in der Mitte teilt. Die entstehenden Teillisten sind dann immer gleich groß.

Wird die Anzahl der zu sortierenden Elemente [math]\displaystyle{ n }[/math] verdoppelt, kommt durch die fortlaufende Halbierung lediglich eine einzige neue Rekursionsebene (ein Baum-Level) hinzu. Dieses Wachstumsverhalten (Wie oft kann ich [math]\displaystyle{ n }[/math] durch 2 teilen, bis 1 übrig bleibt?) wird mathematisch durch den Logarithmus zur Basis 2 ausgedrückt: [math]\displaystyle{ \log_2(n) }[/math].

Zu sortierende Elemente [math]\displaystyle{ n }[/math]	4	8	16	32
Als Zweierpotenz	[math]\displaystyle{ \color{green}{2^2} }[/math]	[math]\displaystyle{ \color{green}{2^3} }[/math]	[math]\displaystyle{ \color{green}{2^4} }[/math]	[math]\displaystyle{ \color{green}{2^5} }[/math]
Anzahl Rekursionsebenen [math]\displaystyle{ \log_2(n) }[/math]	2	3	4	5

Wir haben also insgesamt [math]\displaystyle{ \log_2(n) }[/math] Ebenen. Nun müssen wir noch den Aufwand pro Ebene bestimmen: Obwohl die einzelnen Teillisten nach unten hin immer kürzer werden, verdoppelt sich gleichzeitig ihre Anzahl. Auf jeder einzelnen Ebene müssen daher in der Summe über alle Teillisten hinweg wieder (nahezu) [math]\displaystyle{ n }[/math] Elemente betrachtet und mit den jeweiligen Pivots verglichen werden.

Wir multiplizieren also die Arbeit pro Ebene ([math]\displaystyle{ n }[/math] Vergleiche) mit der Anzahl der Ebenen ([math]\displaystyle{ \log_2(n) }[/math]). Fazit Best-Case: Die Laufzeit beträgt [math]\displaystyle{ \mathcal{O}(n \log n) }[/math].

Average-Case (Durchschnittlicher Fall)

In der Praxis haben wir fast nie den perfekten Best-Case, aber zum Glück auch extrem selten den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40). Auch bei solchen ungleichen Teilungen wächst die Tiefe des Baumes weiterhin nur logarithmisch.

Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf Stochastik und unser Vorwissen zur Harmonischen Reihe zurück. Wir fragen uns: Wie hoch ist die Wahrscheinlichkeit, dass zwei beliebige Elemente (nennen wir sie [math]\displaystyle{ z_i }[/math] und [math]\displaystyle{ z_j }[/math], wobei [math]\displaystyle{ z_i < z_j }[/math]) im Laufe des gesamten Algorithmus direkt miteinander verglichen werden?

Zwei Elemente werden genau dann miteinander verglichen, wenn eines der beiden als Pivot-Element ausgewählt wird, bevor irgendein anderes Element, dessen Wert zwischen [math]\displaystyle{ z_i }[/math] und [math]\displaystyle{ z_j }[/math] liegt, als Pivot gewählt wird.
Zwischen [math]\displaystyle{ z_i }[/math] und [math]\displaystyle{ z_j }[/math] (inklusive der beiden Randelemente) liegen exakt [math]\displaystyle{ k = j - i + 1 }[/math] Elemente.
Gehen wir von einer zufälligen Pivot-Wahl aus, hat jedes dieser [math]\displaystyle{ k }[/math] Elemente die gleiche Chance, zuerst als Pivot gezogen zu werden. Damit [math]\displaystyle{ z_i }[/math] und [math]\displaystyle{ z_j }[/math] verglichen werden, muss exakt [math]\displaystyle{ z_i }[/math] oder [math]\displaystyle{ z_j }[/math] der "Gewinner" dieser Ziehung sein. Da es [math]\displaystyle{ 2 }[/math] günstige Fälle bei [math]\displaystyle{ k }[/math] möglichen Fällen gibt, beträgt die Wahrscheinlichkeit exakt [math]\displaystyle{ \frac{2}{k} }[/math].

Summieren wir diese Wahrscheinlichkeiten (den sogenannten Erwartungswert) für alle möglichen Elementpaare im gesamten Array auf, erhalten wir folgende Doppel-Summe: [math]\displaystyle{ E(X) = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} \frac{2}{j - i + 1} }[/math]

Ersetzt man den Abstand [math]\displaystyle{ (j - i + 1) }[/math] formal durch die Laufvariable [math]\displaystyle{ k }[/math], löst sich die innere Summe auf zu: [math]\displaystyle{ \sum_{k=2}^{n} \frac{2}{k} = 2 \cdot \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right) }[/math]

In der Klammer erkennen wir exakt die Harmonische Reihe wieder! Aus der Mathematik wissen wir, dass die Harmonische Reihe für große [math]\displaystyle{ n }[/math] gegen den natürlichen Logarithmus [math]\displaystyle{ \ln(n) }[/math] konvergiert. Die innere Summe ergibt also maximal ungefähr [math]\displaystyle{ 2 \cdot \ln(n) }[/math]. Da die äußere Summe (die Variable [math]\displaystyle{ i }[/math]) insgesamt [math]\displaystyle{ n }[/math]-mal durchlaufen wird, multiplizieren wir diesen Wert mit [math]\displaystyle{ n }[/math] und erhalten insgesamt rund [math]\displaystyle{ 2n \cdot \ln(n) }[/math] zu erwartende Vergleiche.

Da konstante Vorfaktoren (wie die [math]\displaystyle{ 2 }[/math]) und die Basis des Logarithmus in der asymptotischen Notation ignoriert werden, ist der Beweis erbracht: Fazit Average-Case: Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums sicher gegen die Komplexitätsklasse [math]\displaystyle{ \mathcal{O}(n \log n) }[/math].

Worst-Case (Schlechtester Fall)

Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element der aktuellen Teilliste. Dann enthält eine der Partitionen 0 Elemente und die andere Partition [math]\displaystyle{ n-1 }[/math] Elemente. Der Baum "entartet" zu einer linearen Kette. Hinweis für die Praxis: Wird bei einer naiven Implementierung immer stur das letzte Element als Pivot gewählt, tritt dieser Worst-Case ironischerweise genau dann auf, wenn die Liste bereits aufsteigend oder absteigend sortiert ist!

Der Aufwand für das Vergleichen (Partitionieren) auf der ersten Ebene mit [math]\displaystyle{ n }[/math] Elementen ist proportional zu [math]\displaystyle{ n }[/math]. Nennen wir diesen Aufwand [math]\displaystyle{ c \cdot n }[/math] (wobei [math]\displaystyle{ c }[/math] eine Konstante für die Dauer eines einzelnen Vergleichs ist). Auf der nächsten Ebene müssen wir [math]\displaystyle{ n-1 }[/math] Elemente vergleichen, der Aufwand ist also [math]\displaystyle{ c \cdot (n-1) }[/math]. Danach [math]\displaystyle{ c \cdot (n-2) }[/math] und so weiter.

Wenn wir die Partitionierungszeiten für alle Ebenen aufsummieren, erhalten wir folgende Reihe: [math]\displaystyle{ c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2 }[/math]

Wir klammern [math]\displaystyle{ c }[/math] aus und erkennen die bekannte Gaußsche Summenformel: [math]\displaystyle{ c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n }[/math]

Da in der asymptotischen Laufzeitanalyse konstante Faktoren ([math]\displaystyle{ \frac{c}{2} }[/math]) und niederwertige Terme (wie [math]\displaystyle{ n }[/math]) ignoriert werden, bestimmt allein der quadratische Term das Wachstumsverhalten. Fazit Worst-Case: Quicksort hat im schlechtesten Fall eine Zeitkomplexität von [math]\displaystyle{ \mathcal{O}(n^2) }[/math].