Quicksort

QuickSort (von engl. quick – schnell, to sort – sortieren) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (engl. Divide and conquer) arbeitet. Er wurde 1962 von C. Antony R. Hoare in seiner Grundform erfunden und seitdem von vielen Forschern weiterentwickelt. Der Algorithmus hat den Vorteil, dass er über eine sehr kurze innere Schleife verfügt (was die Ausführungsgeschwindigkeit stark erhöht) und ohne zusätzlichen Speicherplatz auskommt (abgesehen von dem für die Rekursion zusätzlichen benötigten Platz auf dem Aufruf-Stack).

Prinzip

QuickSort wählt ein Element aus der zu sortierenden Liste aus (Pivotelement) und zerlegt die Liste in zwei Teilllisten, eine untere, die alle Elemente kleiner und eine obere, die alle Elemente gleich oder größer dem Pivotelement enthält. Dazu wird zunächst ein Element von unten gesucht, das größer als (oder gleichgroß wie) das Pivotelement und damit für die untere Liste zu groß ist. Entsprechend wird von oben ein kleineres Element als das Pivotelement gesucht. Die beiden Elemente werden dann vertauscht und landen damit in der jeweils richtigen Liste. Der Vorgang wird fortgesetzt, bis sich die untere und obere Suche treffen. Damit sind die oben erwähnten Teillisten in einem einzigen Durchlauf entstanden. Suche und Vertauschung können in-place durchgeführt werden.

Die noch unsortierten Teillisten werden über denselben Algorithmus in noch kleinere Teillisten zerlegt (z. B. mittels Rekursion) und, sobald nur noch Listen mit je einem Element vorhanden sind, wieder zusammengesetzt. Die Sortierung ist damit abgeschlossen.

Beispiel

(Quelle: de.wikipedia.org)

Algorithmus

Die folgenden Zahlenfolgen sind Zwischenausgaben einer Quicksort-Implementierung. Es wird jeweils zunächst die Teilfolge ausgegeben, mit der die Quicksort-Methode "gefüttert" wird. Unterhalb der gestrichelten Linie wird die Zahlenfolge immer dann ausgegeben, wenn ein Tauschvorgang erfolgt ist. Ihre Aufgabe ist es, die Arbeit des Algorithmus nachzuvollziehen und sich die genauen Regeln zu überlegen, nach denen die Array-Zeiger l und r (bzw. in der Grafik oben i und j) im Verlauf des Algorithmus ihre Position ändern. l zeigt zu Beginn eines Durchlaufs auf dem ersten Element der Teilfolge (ganz links), r auf das vorletzte Element (das letzte Element ist das Pivot-Element). Schreiben Sie die Regeln auf!

Funktionsparameter: begin (Zeiger auf erstes Element der Teilfolge), end (Zeiger auf letztes Element der Teilfolge)

• Setze den Zeiger pivot auf das letzte Element der Teilfolge.
• Setze den Zeiger l auf das erste Element der Teilfolge.
• Sezte den Zeiger r auf das vorletzte Element der Teilfolge.
  

WIEDERHOLE 

• Solange das Element an der Stelle l kleiner ist als das Pivot-Element, rücke den Zeiger l um eine Position nach rechts.
• Solange das Element an der Stelle r größer ist als das Pivot-Element und r größer ist als l, rücke den Zeiger l um eine Position nach rechts.
• Wenn r größer ist als l, vertausche die Elemente an den Stellen l bzw. r.
  

SOLANGE WIE r größer ist als l

• Wenn r größer ist als l, tausche das Pivot-Element mit dem Element an der Stelle l.
• Wenn begin kleiner ist als l-1, führe den Quicksort-Algorithmus auf der Teilfolge mit den Grenzen begin und l-1 aus.
• Wenn end größer ist als l+1, führe den Quicksort-Algorithmus auf der Teilfolge mit den Grenzen l+1 und end aus.

Implementierung

/**
* Quicksort-Algorithmus hier implementiert zur Sortierung von char-Arrays.
*
* Als Pivot-Element wird jeweils das letzte Element des übergebenen Arrays benutzt.
*
* @author M. Blanke
* @version 1.1
* @date 01/24/2006
*/

public class Quicksort {

  public static char[] arr = {'a', 'n', 'e', 'x', 'a', 'm', 'p', 'l', 'e'};

  public static void main(String[] args) {
    int n = arr.length-1;
    print(0,n);
    quicksort(0,n);
    print(0,n);
  }

  public static void quicksort(int begin, int end){
    int pivot = end;
    int l = begin;
    int r = end-1;

    do {
      while(arr[l]<arr[pivot]) l++;
      while(arr[r]>arr[pivot] && r>l) r--;
      if(r>l)swap(l,r);
    } while(r>l);

    swap(l,pivot);

    if(l-1>begin) quicksort(begin,l-1);
    if(l+1<end) quicksort(l+1,end);
  }

  public static void swap(int a, int b){
    char temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
  }

  public static void print(int begin, int end){
    System.out.println("");
    for(int i=begin; i<=end; i++){
      System.out.print(arr[i]+ " ");
    }
    System.out.println();
    System.out.println("");
  }

}

Laufzeitbetrachtungen

Zur Untersuchung der Laufzeit lässt sich ein mit Quicksort durchgeführter Sortiervorgang gut als (Binär-) Baum darstellen. Dabei steht ein Knoten jeweils für das aktuell gewählte Pivotelement. Ein linker Sohn ist das Pivot-Element einer linken Teilfolge, ein rechter Sohn ist das Pivot-Element einer rechten Teilfolge. Einelementige Teilfolgen werden im Baum als Knoten ohne Kinder ("Blätter") dargestellt.

Beispiel 1

 5  1 12  6 11 10  3  9  4  8  2  7
 5  1  2  6 11 10  3  9  4  8 12  7
 5  1  2  6  4 10  3  9 11  8 12  7
 5  1  2  6  4  3 10  9 11  8 12  7
 5  1  2  6  4  3  7  9 11  8 12 10
-----------------------------------
 5  1  2  6  4  3  |  9 11  8 12 10
 2  1  5  6  4  3  |  9  8 11 12 10
 2  1  3  6  4  5  |  9  8 10 12 11
-----------------------------------
 2  1  |  6  4  5  |  9  8  | 12 11
 1  2     4  6  5     8  9    11 12
          4  5  6
-----------------------------------
 |  2  |  4  |  6  |  |  9  |  | 12

Der Rekursionbaum für den Sortierdurchgang sieht folgendermaßen aus: 

             7                | 11 Vergleiche
       3           10         | 5 + 4 Vergleiche
    1     5     8      11     | 1 + 2 + 1 + 1 Vergleiche
     2   4 6     9       12   | ------------------------
                              | 25 Vergleiche

Beispiel 2

11  3  4  2  8  9 12  6 10  5  1  7
 1  3  4  2  8  9 12  6 10  5 11  7
 1  3  4  2  5  9 12  6 10  8 11  7
 1  3  4  2  5  6 12  9 10  8 11  7
 1  3  4  2  5  6  7  9 10  8 11 12
-----------------------------------
 1  3  4  2  5  6  |  9 10  8 11 12
 1  3  4  2  5  6     9 10  8 11 12
-----------------------------------
 1  3  4  2  5  |     9 10  8 11 |
 1  3  4  2  5        9 10  8 11
-----------------------------------
 1  3  4  2  |        9 10  8 |
 1  2  4  3           8 10  9
-----------------------------------
 1  |  4  3           | 10  9
       3  4              9 10
-----------------------------------
       |  4              | 10

Der Rekursionbaum für den zweiten Sortierdurchgang sieht folgendermaßen aus: 

Man kann leicht erkennen, dass der Quicksort-Algorithmus im ersten Fall effizienter arbeitet, da bei jedem Aufteilen zwei beinahe gleich große Teilfolgen entstehen. Infolgedessen hat der Rekursionsbaum eine geringere (hier sogar optimale) Höhe. Im zweiten Beispiel kommt es mehrfach vor, dass das Pivot-Element das größte (kleinste) Element einer Teilfolge ist. Ein solches Pivot-Element hat im Rekursionbaum nur einen Nachfolger und verursacht so indirekt eine Erhöhung der Anzahl der Baumebenen.

Man kann also sagen: Je geringer die Höhe (= Anzahl der Baumebenen , die Wurzelebene wird nicht mitgezählt) des Rekursionsbaums, desto effizienter konnte Quicksort die Zahlenfolge zerlegen und bearbeiten. Andererseits gilt: Je höher die Anzahl der Baumebenen, desto weniger effizient gelingt die fortlaufende Aufteilung und damit die Abarbeitung des Algorithmus.

Auch die protokollierte Anzahl der Vergleiche (die Vertauschungen kann man vernachlässigen, da bei Quicksort immer sehr gezielt getauscht wird), die pro Baumebene erfolgen, spiegeln die obigen Überlegungen wider. Ich bin hier davon ausgegangen, das in jeder Teilfolge jedes Nicht-Pivot-Element einmal mit dem Pivot-Element verglichen werden muss. Am Anfang sind es 11 Nicht-Pivot-Elemente, also auf der ersten Baumebene jeweils 11 Vergleiche. (Anmerkung: Unser Quicksort-Algorithmus braucht in beiden Fällen noch mehr Vergleiche, da wir nach Austausch von zwei Pivot-Elementen die Array-Zeiger nicht sofort um ein Element weiter setzen. So kommt es dazu, das zu vertauschende Element zweimal mit dem Pivot-Element verglichen werden.)

Worst Case

Im schlechtesten Fall wird als Pivot-Element immer das größte bzw. kleinste Element einer Teilfolge gewählt. Dies ist zum Beispiel der Fall, wenn eine Zahlenfolge bereits sortiert vorliegt. Es sind dann im Allgemeinen (n-1) + (n-2) + ... + 1 = n · (n - 1) · 0,5 = 0,5 · n^2 - 0,5 · n Vergleiche nötig. Die (n - 1) Summanden entsprechen den (n - 1) Ebenen im Rekursionsbaum. Die Anzahl der Vergleichsoperationen ist also quadratisch von der Anzahl n der Länge der Zahlenfolge abhängig. Damit sortiert Quicksort im Worst Case mit gleichem Aufwand wie BubbleSort oder SelectionSort und liegt in der Aufwandsklasse O(n²).

Best Case

Im besten Fall liegt eine Zahlenfolge vor, deren Rekursionsbaum möglichst flach ist. Betrachten wir eine Zahlenfolge mit den Zahlen 1 bis 7. In diesem Fall ist nur ein optimaler Rekursionsbaum denkbar:

             4               | Ebene 0
       2           6         | Ebene 1
    1     3     5      7     | Ebene 2

Der Baum hat die für 7 Elemente optimale Höhe 2. Ein optimaler Rekursionbaum für n=15 Elemente sieht so aus:

             8               | Ebene 0
       4           12        | Ebene 1
    2     6     10      14   | Ebene 2
   1 3   5 7   9  11  13  15 | Ebene 3

Er hat die Höhe 3. In Abhängigkeit von n ergeben sich folgende Baumhöhen:

n     |  Baumhöhe h
-------------------
1     |  0
2-3   |  1
4-7   |  2
8-15  |  3
16-31 |  4
32-63 |  5
...   |  ...

Man sieht, dass die unteren Grenzen der n-Bereiche jeweils Potenzen zur Basis zwei sind (2^h), die oberen Grenzen immer um Eins kleiner als eine Zweierpotenz (2^h-1).

n  = 2^h  | Baumhöhe h
------------------
1  = 2⁰  | 0
2  = 2¹  | 1
4  = 2²  | 2
8  = 2³  | 3
16 = 2⁴  | 4
32 = 2⁵  | 5
...      |  ...

Nun sieht man deutlich: Der Exponent der Zweierpotenz entspricht der optimalen Baumhöhe. Anders ausgedrückt: Bei gegebenem n berechnet sich die optimale Baumhöhe als Logarithmus von n zur Basis 2: h = log₂ (n). Ist n selbst keine Zweierpotenz gilt diese Formel dennoch, wenn man die Nachkommastellen nach Logarithmieren einfach abschneidet: log₂(6) = 2,58... = Baumhöhe 2 oder log₂(45) = 5,49... = Baumhöhe 5.

Um nun den Aufwand im Best Case für Quicksort abzuschätzen, gehen wir vereinfachend davon aus, dass auf jeder Baumebene n Vergleiche notwendig sind. Tatsächlich werden es, wie wir oben gesehen haben, mit zunehmender Baumtiefe immer weniger Vergleiche. Bei log₂(n) Ebenen lässt sich der Aufwand an Vergleichen durch n·log₂(n) nach oben Abschätzen. Damit gehört der Quicksort-Algorithmus im Best Case in die Aufwandsklasse O(n·log(n)), was eine deutliche Verbesserung gegenüber dem Worst Case darstellt.

Die wahre Stärke von Quicksort ist, dass der Aufwand im Average Case nur wenig größer (nur um etwa 38%) ist als im Best Case. Durch einen konstanten Vorfaktor ändert sich die Aufwandsklasse nicht. Quicksort sortiert im Average Case demnach ebenfalls mit Aufwand O(n·log(n)).

Ein Ansatz, um Worst Case-Laufzeiten zu verhindern, ist, als Pivotelement ein zufällig bestimmtes Element zu wählen. Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit, dass das Pivotelement in jedem Teilungsschritt so gewählt wird, dass sich die worst case-Laufzeit ergibt, extrem gering, so dass man praktisch von einer Komplexität von O(n·log(n)) ausgehen kann. Eine andere Möglichkeit ist die Verwendung des Medians von z.B. drei zufällig gewählten Elementen. Durch geschickte Wahl des Pivotelementes kann man aber nur das mittlere schlechteste Verhalten verbessern. Vollständig verhindern kann man das Eintreten des Worst Case jedoch nicht.

In der Praxis wird der Algorithmus trotz des möglichen Auftretens des schlechtesten Falles verwendet. Er ist heute für ein breites Spektrum von praktischen Anwendungen die bevorzugte Sortiermethode, weil er schnell ist und, sofern Rekursion zur Verfügung steht, einfach zu implementieren ist. In vielen Standard-Bibliotheken ist er bereits vorhanden.

» drucken: pdf | html