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).

Divide and Conquer: Quicksort(n)

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
solange i ≤ j wiederhole

suche von links das erste Element a_i mit a_i ≥ x
suche von rechts das erste Element a_j mit a_j ≤ x
wenn i ≤ j dann

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.

Die folgende Funktion quicksort sortiert ein Teilstück des Arrays a vom Index lo bis zum Index hi. Das Vergleichselement x wird als das mittlere Element zwischen lo und hi gewählt ¹).

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-lo)/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.

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.

Quicksort ist in der angegebenen Implementierung einfach, elegant und schnell. Gleichwohl sind einige Optimierungen möglich, die bei bestimmten Eingabefolgen oder sogar im Durchschnitt zu deutlichen Verbesserungen führen.

Einige Vorschläge zu solchen Optimierungen sind in den Aufgaben zu Sortierverfahren formuliert. Bearbeiten Sie diese Aufgaben und untersuchen Sie, wie sich diese Optimierungen praktisch auf die Laufzeit von Quicksort auswirken.

[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 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)

Quicksort und andere Sortierverfahren, so etwa Heapsort, Mergesort und Shellsort, finden Sie auch in meinem Buch über Algorithmen.
Weitere (vertikaler Abstand) Themen des Buches: Textsuche, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

¹) Die Berechnung lo+(hi-lo)/2 anstelle der einfacheren Berechnung (lo+hi)/2 wird wegen der Gefahr eines Integer-Überlaufs gewählt, der entsteht, wenn lo+hi größer als 2.147.483.647 wird.

Weiter mit: [Heapsort] oder [up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 12.09.1997 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Sortierverfahren

Quicksort

Idee

Programm

Analyse

Zusammenfassung

Aufgaben

Literatur