Sortierverfahren

Quicksort

 English version  aufwärts

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

Idee

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 a0, ..., an-1 mit n Elementen
Ausgabe:Umordnung der Folge derart, dass alle Elemente a0, ..., aj kleiner oder gleich den Elementen ai, ..., an-1 sind (i > j)
Methode:
  1. wähle das mittlere Element der Folge als Vergleichselement x

    setze i = 0 und j = n-1

    solange ikleiner gleichj wiederhole

    1. suche von links das erste Element ai mit aigrößer gleichx

      suche von rechts das erste Element aj mit ajkleiner gleichx

      wenn ikleiner gleichj dann

      1. vertausche ai und aj

        setze i = i+1 und j = j-1

 

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

Simulation (Aufteilungsverfahren)

Folgende Simulation veranschaulicht das Aufteilungsverfahren.

(Java-Applet zur Simulation des Aufteilungsverfahrens von Quicksort)

Programm

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

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

Analyse

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 Θ(n2) 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
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 Θ(n2) Schritte benötigt.

Satz:  Die Zeitkomplexität von Quicksort beträgt

Θ(n log(n))  im Durchschnitt   und
Θ(n2)im schlechtesten Fall.

Simulation

(Java-Applet zur Visualisierung von Quicksort)

Zusammenfassung

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 Θ(n2) 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.

Aufgaben

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.

Literatur

[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]

Buch  

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

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 12.09.1997   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik