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 immer exakt in der Mitte teilt. Die 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. Auf jeder einzelnen Ebene müssen in der Summe [math]\displaystyle{ n }[/math] Elemente betrachtet und mit dem jeweiligen Pivot verglichen werden. Wir multiplizieren also die Arbeit pro Ebene ([math]\displaystyle{ n }[/math]) 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 selten den perfekten Best-Case, aber fast nie den absoluten Worst-Case. Meistens teilt das Pivot die Liste in ungleiche, aber moderate Verhältnisse (z. B. 30:70 oder 60:40).

Um den Average-Case mathematisch exakt zu beweisen, greifen wir auf unser Vorwissen (Indikatorvariablen und Harmonische 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 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.
Sind die Daten völlig zufällig verteilt, hat jedes dieser [math]\displaystyle{ k }[/math] Elemente die gleiche Chance, zuerst als Pivot gewählt 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 ([math]\displaystyle{ z_i }[/math] oder [math]\displaystyle{ z_j }[/math]) 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 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]

Hier erkennen wir exakt die Harmonische Reihe ([math]\displaystyle{ H_n }[/math]) wieder! Da die Harmonische Reihe für große [math]\displaystyle{ n }[/math] gegen den natürlichen Logarithmus [math]\displaystyle{ \ln(n) }[/math] konvergiert, ergibt die innere Summe ungefähr [math]\displaystyle{ 2 \cdot \ln(n) }[/math]. Da die äußere Summe (stark vereinfacht) [math]\displaystyle{ n }[/math]-mal läuft, erhalten wir insgesamt rund [math]\displaystyle{ 2n \cdot \ln(n) }[/math] Vergleiche.

Da konstante Vorfaktoren wie die [math]\displaystyle{ 2 }[/math] beim Groß-O ignoriert werden, ist nun stochastisch bewiesen: Fazit Average-Case: Auch bei zufälliger Verteilung konvergiert Quicksort dank des logarithmischen Wachstums der harmonischen Reihe sicher gegen die Komplexitätsklasse [math]\displaystyle{ \mathcal{O}(n \log n) }[/math].

Worst-Case (Schlechtester Fall)

Betrachten wir zunächst die Worst-Case-Laufzeitanalyse. Angenommen, wir haben extremes Pech und die Partitionierung ist maximal unausgeglichen. Das gewählte Pivot ist immer das absolut kleinste oder größte Element. Dann enthält eine der Partitionen 0 Elemente und die andere Partition [math]\displaystyle{ n-1 }[/math] Elemente.

Der Aufwand für das Vergleichen (Partitionieren) einer 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 Vergleichs ist). Auf der nächsten Ebene müssen wir [math]\displaystyle{ n-1 }[/math] Elemente vergleichen, der Aufwand ist [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 und kleinere Terme (wie [math]\displaystyle{ n }[/math]) ignoriert werden, wächst der Aufwand quadratisch. Fazit Worst-Case: Quicksort hat im schlechtesten Fall eine Zeitkomplexität von [math]\displaystyle{ \mathcal{O}(n^2) }[/math].