Der Quicksort-Algorithmus

Bubble Sort, Insertion Sort und Selection Sort sind alle O(n²): verdoppelt sich die Eingabe, vervierfacht sich ungefähr die Arbeit. Quicksort verfolgt eine grundlegend andere Strategie — statt die gesamte Liste wiederholt zu durchlaufen, teilt es das Problem (ungefähr) in zwei Hälften und rekursiert, was im Schnitt bei O(n log n) landet — dieselbe Komplexitätsklasse wie Merge Sort, aber in der Praxis meist schneller, weil kein zusätzliches Array dafür nötig ist.

Die Idee

Wähle ein Element aus der Liste — das Pivot — und ordne alles andere so um, dass jeder Wert, der kleiner als das Pivot ist, links davon landet, und jeder größere Wert rechts davon. Dieser Schritt heißt Partitionierung. Ist er abgeschlossen, steht das Pivot selbst an seiner endgültigen, korrekten Position: Nichts wird je wieder daran vorbeirücken.

Damit bleiben zwei kleinere, unabhängige Probleme: alles links vom Pivot sortieren und alles rechts davon. Beide auf dieselbe Weise zu lösen — ein Pivot wählen, partitionieren, rekursieren — macht aus einer Partitionierung eine vollständige Sortierung. Im besten und durchschnittlichen Fall halbiert jede Partitionierung die Liste ungefähr, sodass die Rekursion nur log n Ebenen tief ist; multipliziert mit den O(n)-Kosten der Partitionierung pro Ebene ergibt das insgesamt O(n log n).

Implementierung

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
bool settled[N];

// Explicit stack instead of real recursion, so a single partitioning step
// can happen per animation tick instead of the whole sort running at once.
int stackLo[64];
int stackHi[64];
int top = -1;

int lo, hi, pivotIdx, i, j;
bool partitioning = false; // false = need the next range from the stack
bool done = false;
int tick = 0;

void push(int a, int b) {
    if (a <= b) {
        top++;
        stackLo[top] = a;
        stackHi[top] = b;
    }
}

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
        settled[n] = false;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }

    push(0, N - 1);
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (!partitioning) {
            if (top < 0) {
                done = true;
            } else {
                lo = stackLo[top];
                hi = stackHi[top];
                top--;
                if (lo == hi) {
                    settled[lo] = true; // single element: already in place
                } else {
                    pivotIdx = hi; // Lomuto partition: last element is the pivot
                    i = lo - 1;
                    j = lo;
                    partitioning = true;
                }
            }
        } else if (j < hi) {
            if (values[j] < values[pivotIdx]) {
                i++;
                int tmp = values[i];
                values[i] = values[j];
                values[j] = tmp;
            }
            j++;
        } else {
            i++;
            int tmp = values[i];
            values[i] = values[hi];
            values[hi] = tmp;
            settled[i] = true; // pivot has reached its final position
            push(i + 1, hi);
            push(lo, i - 1);
            partitioning = false;
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        if (!done && partitioning && idx == pivotIdx) {
            PlotColor(220, 60, 60);   // current pivot
        } else if (settled[idx]) {
            PlotColor(70, 170, 90);   // in its final position
        } else {
            PlotColor(30, 100, 200);  // not yet settled
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

Echte Rekursion würde für jede Hälfte eine Funktion aufrufen und die Aufrufe der Laufzeit-Stack überlassen, läuft dann aber in einem einzigen Aufruf komplett durch statt einen sichtbaren Schritt nach dem anderen zu machen. Das Sample hält statt echter Rekursion einen expliziten Stack von (lo, hi)-Bereichen, sodass frame() pro Schritt genau einen Partitionierungs-Vergleich ausführen und beim nächsten Mal exakt dort weitermachen kann, wo es aufgehört hat.

Verwendet wird das Lomuto-Partitionsschema: Das Pivot ist immer das letzte Element des aktuellen Bereichs (values[hi]). j durchläuft den Bereich; findet es einen Wert, der kleiner als das Pivot ist, wird dieser direkt hinter i getauscht — i markiert die Grenze zu allem, was bisher als kleiner bestätigt wurde. Erreicht j das Pivot, setzt ein letzter Tausch das Pivot genau hinter diese Grenze — seine finale Position — und beide Hälften werden für später auf den Stack gelegt.

• blau — noch nicht an seiner finalen Position
• rot — das Pivot des Bereichs, der gerade partitioniert wird
• grün — endgültig an seiner Position

Schritt für Schritt durchgerechnet

Die Partitionierung von [5, 1, 4, 2, 8] mit Pivot 8 (dem letzten Element) ist ein kurzes Beispiel, da 8 bereits der größte Wert ist — alles landet links davon, und das Pivot bewegt sich nicht. Typischer ist [4, 2, 8, 5, 1] mit Pivot 1:

Nichts war kleiner als 1, also rückte i nie über lo - 1 vor. Der abschließende Tausch platziert das Pivot an Index 0: [1, 2, 8, 5, 4] — die anderen Elemente haben sich auch bewegt, da die vorangehenden wirkungslosen Vergleiche trotzdem dazu führten, dass j unverändert an ihnen vorbeirückte. Das Pivot 1 steht jetzt korrekt ganz vorne, mit dem (noch unsortierten) Rest [2, 8, 5, 4] rechts davon, bereit für seine eigene, unabhängige Partitionierung.

Warum die Pivot-Wahl wichtig ist

Quicksorts durchschnittlicher Fall von O(n log n) setzt voraus, dass jede Partitionierung die Liste ungefähr halbiert. Das Sample wählt immer das letzte Element als Pivot, was einfach ist, aber eine Schwäche hat: Bei einer bereits sortierten (oder umgekehrt sortierten) Liste ist dieses Pivot jedes Mal der größte oder kleinste verbleibende Wert, sodass eine Seite der Partitionierung immer leer ist. Das degradiert zu n Ebenen Rekursion statt log n, jede mit O(n) Arbeit — insgesamt O(n²), nicht besser als die einfachen Sortierverfahren. Produktions-Implementierungen vermeiden das, indem sie das Pivot anders wählen: ein zufälliges Element, den Median einiger Stichproben, oder (wie bei introsort, das die meisten std::sort-Implementierungen verwenden) einen Rückfall auf Heapsort, sobald die Rekursion verdächtig tief wird.

Anders als Merge Sort braucht Quicksort kein Hilfsarray — die Partitionierung arbeitet in-place — was der Hauptgrund dafür ist, dass es in der Praxis meist gewinnt, obwohl beide dieselbe durchschnittliche Komplexität teilen.

Fazit

Während die einfachen Sortierverfahren alle eine feste, quadratische Menge an Vergleichsarbeit leisten, unabhängig von der Struktur, verwandelt Quicksorts Divide-and-Conquer-Ansatz das Sortieren von n Elementen in log n Runden zu je O(n) Partitionierung — solange die Pivot-Wahl die Hälften ungefähr ausgeglichen hält. Dieser Tausch — ein Worst Case, der von der Eingabereihenfolge abhängt, gegen einen deutlich besseren Normalfall — steckt hinter den meisten O(n log n)-Sortieralgorithmen, und Quicksort bleibt eine der klarsten Möglichkeiten, das in Aktion zu sehen.