Sortierverfahren

Quicksort

Der Quicksort-Algorithmus [Hoa 62] ist eines der schnellsten und zugleich einfachsten Sortierverfahren. Das Verfahren arbeitet rekursiv nach dem Divide-and-Conquer-Prinzip.

Bild 1 zeigt schematisch die Vorgehensweise von Quicksort anhand einer Eingabefolge von Nullen (weiß) und Einsen (grau). Zunächst wird die zu sortierende Folge a so in zwei Teilstücke b und c zerlegt, dass alle Elemente des ersten Stücks b kleiner oder gleich allen Elementen des zweiten Stücks c sind (divide). Danach werden die beiden Teilstücke sortiert, und zwar rekursiv nach demselben Verfahren (conquer). Wieder zusammengesetzt ergeben die Teilstücke die sortierte Folge (combine).

Bild 1: Quicksort(n)

Die Aufteilung geschieht, indem zunächst ein Vergleichselement x gewählt wird. Alle Elemente der Folge, die kleiner als x sind, kommen in das erste Teilstück. Alle Elemente, die größer als x sind, kommen in das zweite Teilstück. Bei Elementen, die gleich x sind, ist es egal, in welches Teilstück sie kommen.

In dem folgenden Aufteilungsverfahren kann es auch vorkommen, dass ein Element, das gleich x ist, zwischen den beiden Teilstücken verbleibt. Dieses Element steht dann schon an seiner richtigen Position.


Algorithmus `Partition`
Eingabe:	Folge `a`₀, ..., `a`_n-1 mit `n` Elementen
Ausgabe:	Umordnung der Folge derart, dass alle Elemente `a`₀, ..., `a`_j kleiner oder gleich den Elementen `a`_i, ..., `a`_n-1 sind (`i` > `j`)
Methode:	wähle das mittlere Element der Folge als Vergleichselement `x`; setze `i` = 0 und `j` = `n`-1; wiederhole solange `ij` suche von links das erste Element `a`_i mit `a`_i`x`; suche von rechts das erste Element `a`_j mit `a`_j`x`; falls `ij` vertausche `a`_i und `a`_j; setze `i` = `i`+1 und `j` = `j`-1;

Quicksort behandelt nach dieser Aufteilung der Folge die beiden Teilstücke a₀, ..., a_j und a_i, ..., a_n-1 nach demselben Verfahren rekursiv weiter. Wenn ein im Verlauf des Verfahrens entstehendes Teilstück nur aus einem Element besteht, endet die Rekursion.

Folgende Simulation veranschaulicht das Aufteilungsverfahren.

(Java-Applet zur Simulation des Aufteilungsverfahrens von Quicksort)

Die folgende Funktion quicksort sortiert ein Teilstück des Arrays a vom Index lo bis zum Index hi.

Die Sortierfunktion ist in der Klasse QuickSorter gekapselt. Die Methode sort übergibt das zu sortierende Array an das Array a, setzt n auf dessen Länge und ruft quicksort mit dem unteren Index 0 und dem oberen Index n-1 auf.

Die Hilfsfunktion exchange(i, j) vertauscht die Array-Elemente a[i] und a[j].

Mit den Anweisungen

QuickSorter s=new QuickSorter();
s.sort(b);

wird ein Objekt vom Typ QuickSorter erzeugt und anschließend die Methode sort zum Sortieren eines Arrays b aufgerufen. Es folgt das Programm.

public class QuickSorter
{
    private int[] a;
    private int n;

    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        quicksort(0, n-1);
    }

    private void quicksort (int lo, int hi)
    {
        int i=lo, j=hi;

        // Vergleichselement x
        int x=a[(lo+hi)/2];

        //  Aufteilung
        while (i<=j)
        {    
            while (a[i]<x) i++; 
            while (a[j]>x) j--;
            if (i<=j)
            {
                exchange(i, j);
                i++; j--;
            }
        }

        // Rekursion
        if (lo<j) quicksort(lo, j);
        if (i<hi) quicksort(i, hi);
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }

}    // end class QuickSorter

Der Algorithmus verläuft optimal, wenn jeder Aufteilungsschritt im Verlauf der Rekursion jeweils etwa gleichlange Teilstücke erzeugt. In diesem günstigsten Fall benötigt Quicksort Θ(n log(n)) Schritte, denn die Rekursionstiefe ist dann log(n) und in jeder Schicht sind n Elemente zu behandeln (Bild 2 a).

Der ungünstigste Fall tritt ein, wenn ein Teilstück stets nur aus einem Element und das andere aus den restlichen Elementen besteht. Dann ist die Rekursionstiefe n-1 und Quicksort benötigt Θ(n²) Schritte (Bild 2 c).

Im Mittel wird etwa eine Aufteilung wie in Bild 2 b dargestellt zustande kommen.

Bild 2: Rekursionstiefe von Quicksort: (a) im besten Fall, (b) im Mittel, (c) im schlechtesten Fall

Die Wahl des Vergleichswertes x spielt die entscheidende Rolle dafür, welche Aufteilung zustande kommt. Man könnte z.B. auch das erste Element der Folge als Vergleichselement wählen. Dies würde aber dazu führen, dass das ungünstigste Verhalten des Algorithmus ausgerechnet dann eintritt, wenn die Folge zu Anfang bereits sortiert ist. Daher ist es besser, das mittlere Element der Folge zu wählen.

Am besten ist es natürlich, als Vergleichselement dasjenige Element zu wählen, das von der Größe her in der Mitte der Elemente liegt (der Median). Dann würde die optimale Aufteilung zustande kommen. Tatsächlich ist es möglich, den Median in linearer Zeit zu bestimmen (linearer Medianalgorithmus). In dieser Variante würde Quicksort also auch im schlechtesten Fall nur O(n log(n)) Schritte benötigen.

Quicksort lebt jedoch von seiner Einfachheit. Außerdem zeigt es sich, dass Quicksort auch in der einfachen Form im Durchschnitt nur O(n log(n)) Schritte benötigt. Überdies ist die Konstante, die sich in der O-Notation verbirgt, sehr klein. Wir nehmen dafür in Kauf, dass Quicksort im (seltenen) schlechtesten Fall Θ(n²) Schritte benötigt.

Satz: Die Zeitkomplexität von Quicksort beträgt

Θ(`n` log(`n`))	im Durchschnitt und
Θ(`n`²)	im schlechtesten Fall.

(Java-Applet zur Visualisierung von Quicksort)

Quicksort erweist sich in der Praxis als das schnellste Sortierverfahren. Es hat eine Zeitkomplexität von Θ(n log(n)) im Durchschnitt. Im (seltenen) schlechtesten Fall ist es mit einer Zeitkomplexität von Θ(n²) allerdings genauso langsam wie Insertionsort.

Es gibt Sortierverfahren, die auch im schlechtesten Fall in O(n log(n)) liegen, z.B. Heapsort und Mergesort. Diese sind jedoch im Durchschnitt um einen konstanten Faktor langsamer als Quicksort.

Es ist möglich, mit einer Variante von Quicksort auch im schlechtesten Fall eine Zeitkomplexität von O(n log(n)) zu erreichen (indem als Vergleichselement der Median gewählt wird). Dieses Verfahren ist jedoch im Durchschnitt und im schlechtesten Fall um einen konstanten Faktor langsamer als Heapsort oder Mergesort; daher ist es für die Praxis nicht interessant.


[CLRS 01]	T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2. Auflage, The MIT Press (2001)
[Hoa 62]	C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962)
[Sed 88]	R. Sedgewick: Algorithms. 2. Auflage, Addison-Wesley (1988)

[Lan 06]	H.W. Lang: Algorithmen in Java. 2. Auflage, Oldenbourg (2006) Quicksort und andere Sortierverfahren, so etwa Heapsort, Mergesort und Shellsort, finden Sie auch in meinem Buch über Algorithmen. Weitere Themen des Buches: Textsuche, Parsen und Übersetzen, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen. [Weitere Informationen] [Bestellen]