Quicksort

aus Wikipedia, der freien Enzyklopädie

Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen das Pivotelement im jeweiligen Rekursionsschritt.

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 1960 von C. Antony R. Hoare in seiner Grundform entwickelt und seitdem von vielen Forschern verbessert. 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).

Eine zufällige Permutation des Umfangs n, in der jedes Element von 1 bis n lediglich einmal vorkommt, wird mit Quicksort sortiert.

[Bearbeiten] Prinzip

Quicksort wählt ein Element aus der zu sortierenden Liste aus (Pivotelement) und zerlegt die Liste in zwei Teillisten, eine untere, die alle Elemente kleiner und eine obere, die alle Elemente gleich oder größer dem Pivotelement enthält. Diese Teillisten werden rekursiv sortiert. Anschließend wird das Ergebnis zusammengesetzt. Es besteht (in der Reihenfolge) aus der unteren Liste, dem Pivotelement und der oberen Liste.

Eine direkte Implementation dieses Prinzips hat allerdings den Nachteil, dass sie zum einen zusätzlichen Speicher benötigt und zum anderen unnötig viele Operationen durchführt. Deshalb wird ein Verfahren verwendet, das als teilen oder auch partitionieren bezeichnet wird. Dieses arbeitet in-place. Hierbei wird nach der Wahl des Pivotelementes zunächst ein Element vom Anfang der Liste beginnend gesucht, das größer als (oder gleichgroß wie) das Pivotelement und damit für die untere Liste zu groß ist. Entsprechend wird vom Ende der Liste beginnend 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. Auf diese Art und Weise entstehen die beiden Teillisten aus der Gesamtliste. Sie haben auch schon die richtige Position. Es müssen nur noch die Teillisten sortiert werden.

[Bearbeiten] Laufzeit

Die Laufzeit des Algorithmus hängt im wesentlichen von der Wahl des Pivotelementes ab.

Im Worst Case (schlechtesten Fall) wird das Pivotelement stets so gewählt, dass es das größte oder das kleinste Element der Liste ist. Dies ist etwa der Fall, wenn als Pivotelement stets das Element am Ende der Liste gewählt wird und die zu sortierende Liste bereits sortiert vorliegt. Die zu untersuchende Liste wird dann in jedem Rekursionsschritt nur um eins kleiner und die benötigte Rechenzeit ist asymptotisch genau n².

Im Best Case (bester Fall) wird das Pivotelement stets so gewählt, dass die entstehenden Teillisten beide gleich groß sind. In diesem Fall ist die Laufzeit des Algorithmus durch O(n·log(n)) nach oben beschränkt. Auch für den durchschnittlichen Fall gilt diese obere Schranke.

Für die Wahl des Pivotelementes sind in der Literatur verschiedene Ansätze beschrieben worden. Die Wahrscheinlichkeit des Eintreffens des Worst Case ist bei diesen unterschiedlich groß, aber immer ungleich Null.

Ein möglicher Ansatz ist es, immer das erste, das letzte oder das mittlere Element der Liste zu wählen. Dieser naive Ansatz ist aber relativ ineffizient. Eine andere Möglichkeit ist es den Median dieser drei Elemente zu bestimmen und als Pivotelement zu verwenden. Ein anderer Ansatz ist, als Pivotelement ein zufälliges Element auszuwä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. Man kann davon ausgehen, dass er praktisch nie auftritt.

Durch die geschickte Wahl des Pivotelementes kann das mittlere schlechteste Verhalten verbessert werden. Das Eintreten des Worst Case kann sogar ausgeschlossen werden, wenn als Pivotelement stets der Median der zu sortierenden Folge gewählt wird. Die Berechnung des Median ist für konstantes c in c·n Schritten möglich, wodurch auch im Worst Case eine Gesamtlaufzeit von O(n·log (n)) garantiert wäre. Allerdings führt dieser Ansatz nicht zu einem praktisch effizienten Sortieralgorithmus, da c zu groß ist.

Es gibt Algorithmen, wie z.B. Heapsort, deren Laufzeit auch im Worst Case durch O(n·log(n)) beschränkt sind. In der Praxis wird aber trotzdem Quicksort eingesetzt. Der Worst Case tritt nur sehr selten auf und im mittleren Fall ist Quicksort schneller, da die innerste Schleife von Quicksort nur einige wenige, sehr einfache Operationen enthält. Heute ist Quicksort 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 Standardbibliotheken ist er bereits vorhanden. Mittlerweile steht jedoch mit Introsort auch eine Alternative zur Verfügung, die bei vergleichbarer mittlerer Laufzeit auch für den Worst Case eine obere Schranke von O(n·log(n)) garantiert.

Quicksort setzt jedoch voraus, dass effizient (d.h. mit Aufwand O(1)) über einen Index auf die Elemente zugegriffen werden kann. Dies ist jedoch meist nur bei Arrays der Fall. Für verkettete Listen sind andere Sortieralgorithmen meist effizienter, wie etwa adaptiertes 2-Phasen-2-Band-Mischen oder Mergesort. Andere dynamische Datenstrukturen wie balancierte Bäume (B-Bäume, AVL-Bäume oder 2-3-4-Bäume, letztere meist implementiert als Rot-Schwarz-Baum) verteilen die Kosten des Sortierens auf die Einfügeoperationen, so dass nachträgliches Sortieren nicht notwendig ist.

[Bearbeiten] Implementierung

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei daten das zu sortierende Feld ist. Dabei ist wichtig zu erwähnen, dass links die linke Grenze also der Startwert 0 (als erstes Element des Arrays) und der Startwert von rechts n (das letzte Feld des Arrays) ist:

 funktion quicksort(links, rechts);
   falls rechts > links;
     teiler := teile(links, rechts);
     quicksort(links, teiler-1);
     quicksort(teiler+1, rechts);

Die Funktion teile muss dabei das Feld so teilen, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen, zum Beispiel durch

 funktion teile(links, rechts);
   index := links;
   von zeiger := links bis rechts-1;
     falls daten[zeiger] <= daten[rechts];
       tausche(index, zeiger);
       index := index + 1;
   tausche(index, rechts);
   antworte index;

 funktion tausche(a, b)
   temp := daten[a]
   daten[a] := daten[b]
   daten[b] := temp

Eine abgewandelte Version der Funktion teile ist die folgende:

 funktion teile(links, rechts)
   i := links-1
   j := rechts
   pivot := rechts
   fürimmer
     // Suche von links ein Element, das >= daten[pivot] ist
     i := i + 1
     solange daten[i] < daten[pivot]
        i := i + 1  
     // Suche von rechts ein Element, das < daten[pivot] ist
     j := j - 1
     solange (daten[pivot] < daten[j]) und (j > links)
        j := j - 1 
     // Abbruch, wenn sich i und j "kreuzen"
     falls i >= j
        abbruch
     // vertausche zwei unpassende Elemente
     tausche(i, j)
   endefürimmer
   // setze Pivot an die richtige Stelle und gib seine Position zurück
   tausche(i, pivot)
   antworte i;

[Bearbeiten] Beispiel teile(l,r)

[Bearbeiten] 1. Variante

¹ Eigentlich wird das erste Element mit sich selbst vertauscht, da Zeiger und Index auf dem gleichen Element liegen. Dies hat aber keine sichtbare Auswirkung.

[Bearbeiten] 2. Variante

[Bearbeiten] Varianten

Die Effizienz von Quicksort liegt darin, dass es Elemente aus großer Distanz miteinander vertauscht. Je kürzer die zu sortierende Liste wird, desto ineffizienter arbeitet Quicksort, da es sich einer Komplexität von O(n²) nähert. Die von Quicksort in Teillisten zerlegte Liste hat jedoch die Eigenschaft, dass der Abstand zwischen einem Element und seiner sortierten Position nach oben beschränkt ist. Eine solche Liste sortiert Insertionsort in linearer Zeit, so dass häufig in der Implementierung unterhalb einer definierten Teillistenlänge der Quicksort abgebrochen wird, um mit Insertionsort weiterzusortieren.

Siehe auch: Introsort

[Bearbeiten] Weitere Sortierverfahren

• Shellsort
• Heapsort (siehe auch Heap)
• Mergesort
• Bubblesort
• Insertionsort
• Selectionsort

Siehe auch: Sortierverfahren

[Bearbeiten] Literatur

• Robert Sedgewick: Algorithmen. Pearson Studium 2002 ISBN 3827370329
• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein: Introduction to Algorithms (Second Edition), ISBN 0262032937 – ein Standardwerk zu Algorithmen

[Bearbeiten] Weblinks

• Vollständiger Quicksort-Artikel auf www.linux-related.de
• Java-Applet und Code zur Visualisierung
• Überblick über mögliche Geschwindigkeitsoptimierungen
• Verstehen durch Schritt-für-Schritt Ausprobieren
• VisuSort Framework – Visualisierung diverser Sortieralgorithmen (Windows)
• Pseudocode zu Quicksort und seinen Varianten
• Robert F. Stärk: Animated Sorting Algorithms – Java-Beispiele
• Beispiel zum Teilen der Daten
• Einfache graphische Darstellung und ausführliche Wahrscheinlichkeitsanalyse des randomisierten Quicksort
• Videoerklärung von Quicksort mit Karten und Code in C++- einfach zu Verstehen