Quicksort

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen den Wert des rot markierten Pivotelements im jeweiligen Rekursionsschritt.

Quicksort (engl. quick ‚schnell‘ und to sort ‚sortieren‘) ist ein schneller, rekursiver, nicht-stabiler Sortieralgorithmus, der nach dem Prinzip Teile und herrsche (lat. Divide et impera!, engl. divide and conquer) arbeitet. Er wurde ca. 1960 von C. Antony R. Hoare in seiner Grundform entwickelt[1] 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).

Im Durchschnitt führt der Quicksort-Algorithmus O(n log n) Vergleiche durch. Im schlechtesten Fall werden O(n2) Vergleiche durchgeführt, was aber in der Praxis sehr selten vorkommt[2].

Die Zahlen von 1 bis n in zufälliger Reihenfolge werden mit Quicksort sortiert.

Prinzip[Bearbeiten]

Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

Anschließend muss man also nur noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion.

Die Positionen der Elemente, die gleich dem Pivotelement sind, hängen vom verwendeten Teilungsalgorithmus ab. Sie können sich beliebig auf die Teillisten verteilen. Da sich die Reihenfolge von gleichwertigen Elementen zueinander ändern kann, ist Quicksort im Allgemeinen nicht stabil (stabile in-place Varianten existieren jedoch [3]).

Das Verfahren muss sicherstellen, dass jede der Teillisten mindestens um eins kürzer ist als die Gesamtliste. Dann endet die Rekursion garantiert nach endlich vielen Schritten. Das kann z. B. dadurch erreicht werden, dass das ursprünglich als Pivot gewählte Element auf einen Platz zwischen den Teillisten gesetzt wird und somit zu keiner Teilliste gehört.

Pseudocode[Bearbeiten]

Die Implementierung der Teilung erfolgt als In-place-Algorithmus: Die Elemente werden nicht in zusätzlichen Speicher kopiert, sondern nur innerhalb der Liste vertauscht. Dafür wird ein Verfahren verwendet, das als teilen oder auch partitionieren bezeichnet wird. Danach sind die beiden Teillisten gleich in der richtigen Position. Sobald die Teillisten in sich sortiert wurden, ist die Sortierung der Gesamtliste beendet.

Der folgende Pseudocode illustriert die Arbeitsweise des Algorithmus, wobei daten die zu sortierende Liste mit n Elementen ist. Bei jedem Aufruf von quicksort() gibt links den Index des ersten Elements in der Teilliste an und rechts den des letzten. Beim ersten Aufruf (oberste Rekursionsebene) ist links = 0 und rechts = n-1. Die übergebene Liste wird dabei rekursiv immer weiter geteilt, bis sie nur noch einen Wert enthält.

 funktion quicksort(links, rechts)
     falls links < rechts dann
         teiler := teile(links, rechts)
         quicksort(links, teiler-1)
         quicksort(teiler+1, rechts)
     ende
 ende

Die folgende Implementierung der Funktion teile teilt das Feld so, dass sich das Pivotelement an seiner endgültigen Position befindet und alle kleineren Elemente davor stehen, während alle größeren danach kommen:

 funktion teile(links, rechts)
     i := links 
     // Starte mit j links vom Pivotelement
     j := rechts - 1
     pivot := daten[rechts]

     wiederhole

         // Suche von links ein Element, welches größer als das Pivotelement ist
         wiederhole solange daten[i] ≤ pivot und i < rechts
             i := i + 1
         ende

         // Suche von rechts ein Element, welches kleiner als das Pivotelement ist
         wiederhole solange daten[j] ≥ pivot und j > links
              j := j - 1 
         ende

         falls i < j dann
             tausche daten[i] mit daten[j]
         ende

     solange i < j // solange i an j nicht vorbeigelaufen ist 

     // Tausche Pivotelement (daten[rechts]) mit neuer endgültiger Position (daten[i])
   
     falls daten[i] > pivot dann
             tausche daten[i] mit daten[rechts]
     ende
     
     // gib die Position des Pivotelements zurück
    
     antworte i
 ende

Nach der Wahl des Pivotelementes wird zunächst ein Element vom Anfang der Liste beginnend gesucht (Index i), welches größer als das Pivotelement ist. Entsprechend wird vom Ende der Liste beginnend ein Element kleiner als das Pivotelement gesucht (Index j). Die beiden Elemente werden dann vertauscht und landen damit in der jeweils richtigen Teilliste. Dann werden die beiden Suchvorgänge von den erreichten Positionen fortgesetzt, bis sich die untere und obere Suche treffen; dort ist die Grenze zwischen den beiden Teillisten.

Beispiele[Bearbeiten]

teile(links, rechts)[Bearbeiten]

Die Buchstabenfolge „einbeispiel“ soll alphabetisch sortiert werden.

Ausgangssituation nach Initialisierung von i und j, das Element rechts (l) ist das Pivotelement:

  e i n b e i s p i e l
^                     ^
i                     j

Nach der ersten Suche in den inneren Schleifen hat i auf einem Element >= l und j auf einem Element <= l gehalten:

  e i n b e i s p i e l
      ^             ^
      i             j

Nach dem Tauschen der Elemente bei i und j:

  e i e b e i s p i n l
      ^             ^
      i             j

Nach der nächsten Suche und Tauschen:

  e i e b e i i p s n l
              ^   ^
              i   j

Nach einer weiteren Suche sind die Indizes aneinander vorbeigelaufen:

  e i e b e i i p s n l
              ^ ^
              j i

Nach dem Tauschen von i und Pivot bezeichnet i die Trennstelle der Teillisten. Bei i steht das Pivot-Element, links davon sind nur Elemente <= Pivot und rechts nur solche > Pivot:

  e i e b e i i l s n p
                ^
                i

Vollständiges Beispiel für alphabetische Sortierung[Bearbeiten]

In diesem Beispiel soll der Quicksortalgorithmus die Buchstabenfolge "Quicksort" sortieren. Zunächst wird das rechte Element P-> als Pivotelement definiert. Dann laufen die Zähler g für "größer" von links nach rechts und k für "kleiner" von rechts nach links los,

 Quicksort
^       ^^
g       kP

bis g auf ein Element trifft, welches größer als das Pivotelement ist und bis k auf ein Element trifft, welches kleiner ist als das Pivotelement.

 Quicksort
  ^     ^^
  g     kP

Diese beiden gefundenen Elemente r und u werden dann im folgenden Schritt getauscht.

 Qricksout
  ^     ^^
  g     kP

Im folgenden Schritt laufen die Indizes k und g in der gleichen Richtung wie gehabt weiter und suchen Elemente, die bei k kleiner und bei g größer als das Pivotelement sind.

 Qricksout
       ^^^
       kgP

Jetzt sind k und g aneinander vorbeigelaufen. Dieses Ereignis ist eine Abbruchbedingung. Jetzt wird das Pivotelement mit dem durch g indizierten Element getauscht.

 Qricksotu
       ^^^
       kPg

Jetzt treffen folgende zwei Aussagen zu: "Links des Pivotelements sind alle Elemente kleiner oder gleich dem Pivotelement. Rechts des Pivotelements sind alle Elemente grösser oder gleich dem Pivotelement."

   links|:|rechts
 Qrickso|t|u
       ^|^|^
       k|P|g

Das Pivotelement "teilt" nun die Datenmenge an der Stelle des Pivotelements in zwei Hälften Links und Rechts. Nun muss der Algorithmus den linken und den rechten Teil auf die gleiche Weise wie im Vorangehenden schon geschehen weiterbehandeln. Hierdurch ergibt sich nun die Rekursion. Der rechte Teil (Der Buchstabe u) ist nur ein einzelnes Element und ist somit per Definition sortiert. Also wird nun der linke Teil behandelt. Das rechte Element ist wieder das Pivotelement, und die Zähler werden passend gesetzt.

 Qrickso|t|u
^     ^^
g     kP

Das Q ist größer als o und das k ist kleiner als das o.

 Qrickso|t|u
 ^   ^ ^
 g   k P

Also werden das Q und das k vertauscht.

 kricQso|t|u
 ^   ^ ^
 g   k P

Indizes g und k laufen weiter...

 kricQso|t|u
  ^ ^  ^
  g k  P

Das r und das c werden getauscht.

 kcirQso|t|u
  ^ ^  ^
  g k  P

Im folgenden Schritt sind die Indizes wieder aneinander vorbeigelaufen...

 kcirQso|t|u
   ^^  ^
   kg  P

... und das Pivotelement (Buchstabe o) wird mit dem größeren Element (Buchstabe r) getauscht.

 kcioQsr|t|u
   ^^  ^
   kP  g

Nun ergibt sich erneut ein linker und ein rechter Teil.

links:rechts
 kci|o|Qsr  |t|u
   ^|^|  ^  | |
   k|P|  g  | |

Zunächst wird der linke Teil behandelt.

     :
 kci|o| Qsr|t|u
^ ^^| |^ ^^| |
g kP| |g kP| |
     :
 cki|o| Qsr|t|u
 ^^^| |^ ^^| |
 gkP| |g kP| |

Buchstabe c und k werden getauscht.

     :
 cki|o| Qsr|t|u
 ^^^| |^ ^^| |
 kgP| |g kP| |

Indizes sind aneinander vorbeigelaufen, und das Element des Index g wird mit dem des Index P vertauscht.

     :
 cik|o| Qsr|t|u
 ^^^| |^ ^^| |
 kPg| |g kP| |

Der jetzt entstandene neue linke und rechte Teil besteht nun nur noch aus einem einzelnen Element und gilt als sortiert.

     :
 cik|o| Qsr|t|u
    | | ^^^| |
    | | kgP| |

Im ehemals rechten Teil (Buchstaben Qsr) laufen die Indizes direkt aneinander vorbei, und das Element bei g wird mit dem Pivotelement getauscht.

     :
 cik|o| Qrs|t|u
    | | ^^^| |
    | | kPg| |

Damit sind alle Zeichen sortiert.

 cik|o| Qrs|t|u
 Ergebnis:
 cikoQrstu

Kenngrößen[Bearbeiten]

Laufzeit[Bearbeiten]

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 Zeitkomplexität wird beschrieben durch \mathcal{O}(n^2).

Im Best Case (bester Fall) wird das Pivotelement stets so gewählt, dass die beiden entstehenden Teillisten etwa gleich groß sind. In diesem Fall gilt für die asymptotische Laufzeit des Algorithmus  \mathcal{O}(n \cdot \log (n)) . Diese Zeitkomplexität gilt ebenso für den Average Case (durchschnittlichen Fall). Die Länge der jeweils längeren Teilliste beim rekursiven Aufruf ist nämlich im Schnitt \textstyle \frac{2}{n} \sum\limits_{i=\frac{n}{2}}^{n-1} i =  \frac{3}{4}n - \frac{3}{2} und die Tiefe der Rekursion damit in \mathcal{O}(\log n) .

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

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.

Es gibt Algorithmen, beispielsweise Heapsort, deren Laufzeit auch im Worst Case durch  \mathcal{O}(n \cdot \log (n)) beschränkt sind. In der Praxis wird aber trotzdem Quicksort eingesetzt, da angenommen wird, dass bei Quicksort der Worst Case nur sehr selten auftritt und im mittleren Fall schneller als Heapsort ist, da die innerste Schleife von Quicksort nur einige wenige, sehr einfache Operationen enthält. Dies ist jedoch noch Forschungsgegenstand und einige Analysen und Simulationen sehen Heapsortvarianten vorne, sowohl aus informationstheoretischen Überlegungen wie Implementierungsbetrachtungen.[4][5]

Heute ist Quicksort für ein breites Spektrum von praktischen Anwendungen der bevorzugte Sortieralgorithmus, 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  \mathcal{O}(n \cdot \log (n)) garantiert.

Speicherplatz[Bearbeiten]

Quicksort ist ein in-Place-Verfahren. Es vertauscht zwar die Elemente der zu sortierenden Liste nur innerhalb der Liste und kopiert sie nicht in zusätzlichen Speicherplatz. Es benötigt jedoch für jede Rekursionsebene zusätzlichen Platz auf dem Stack.

Wie bei der Laufzeit hängt auch der Speicherverbrauch von der Wahl des Pivotelements und der Art der vorliegenden Daten ab. Im günstigsten und durchschnittlichen Fall, bei einer Rekursionstiefe in  \mathcal{O}(\log (n)) , wird auch nur eine Stapelgröße von  \mathcal{O}( \log (n)) benötigt.

Im ungünstigsten Fall ist die Anzahl der Rekursionen nur durch die Listenlänge n beschränkt, was einen Stapel der Größe  \mathcal{O}(n ) erfordert. Dies kann bei langen Listen zu einem Stapelüberlauf führen. Es gibt vielfältige Modifikationen des Algorithmus um dieses Problem zu lösen oder zumindest die Wahrscheinlichkeit seines Auftretens zu vermindern[6]:

  • Endrekursionsbeseitigung (siehe nachfolgenden Pseudocode)
  • eine ausgewogenere Wahl des Pivotelements (z. B. Median von Drei)
  • Wahl eines zufälligen Pivotelements, wodurch systematische Probleme vermieden werden, die sich sonst durch bestimmte Vorsortierungen der Elemente im Zusammenspiel mit der Methode der Pivotwahl ergeben können
  • Vermeidung von Teillisten mit weniger als zwei Elementen (ergibt, wenn auch das Pivotelement aus den Teillisten genommen wird, die maximale Rekursionstiefe n/3)

Der folgende Pseudocode ersetzt die Endrekursion (Sortierung der zweiten Teilliste) durch eine Iteration derart, dass die kürzere Teilliste rekursiv und die längere iterativ sortiert wird. Die Rekursionstiefe ist dann nicht größer als log(n):

 funktion quicksort(links, rechts)
     solange rechts > links wiederhole
         teiler := teile (links, rechts)
         falls rechts-teiler > teiler-links
            quicksort(links, teiler - 1) // kleinere Teilliste rekursiv ..
            links := teiler + 1 // .. und größere iterativ sortieren
         sonst
            quicksort(teiler + 1, rechts)
            rechts := teiler - 1
         ende
     ende
 ende

Eine weitere Möglichkeit den in n linearen zusätzlichen Speicherplatz zu vermeiden besteht darin, dass man zuerst die kleinere der beiden Teilfolgen rekursiv sortiert (die andere wird danach sortiert, aber ebenfalls rekursiv). Somit bleibt die Anzahl der noch nicht sortierten Teilfolgen durch \mathcal{O}(\log (n) ) beschränkt. Für jede noch nicht sortierte Teilfolge werden zwei Indexgrenzen gespeichert, die jeweils \mathcal{O}(log(n) ) zusätzlichen Speicherplatz benötigen. Insgesamt benötigt Quicksort mit dieser Variante \mathcal{O}(\log^2(n) ) zusätzlichen Speicherplatz im logarithmischen Kostenmaß.

Varianten[Bearbeiten]

QuickSort für verkettete Listen[Bearbeiten]

Bei nachfolgend dargestellter QuickSort-Variante für verkettete Listen wird als Pivotelement das jeweils erste der zu teilenden Folge gewählt. Ein Zeiger Ptr2 wird soweit vorgeschoben, bis er auf ein Element trifft, das kleiner als das Pivot ist. Die Elemente, über die Ptr2 hinweggegangen ist, sind demzufolge größer oder gleich dem Pivot. Ein Tausch des ersten dieser größeren Elemente mit dem bei Ptr2 sorgt also dafür, dass die betreffenden Elemente im richtigen Teilabschnitt landen. Ptr1 markiert das aktuelle Ende des Teilabschnitts der Elemente, die kleiner als das Pivot sind. Wenn Ptr2 am rechten Rand der zu teilenden Folge angelangt ist, wird abschließend das Pivotelement an die richtige Position zwischen den Teilfolgen getauscht.

 QuickSort(Links,Rechts);
 //Links, Rechts sind hier Zeiger
  falls Links<>Rechts dann
     Ptr1:=Links
     Ptr2:=Links
     Ptr0:=Links
     //Initialisierung der (lokalen) Zeiger; Ptr0 wird nur als Vorgänger von Ptr1 benötigt
     Pivot:=Links.Zahl
     wiederhole
        Ptr2:=Ptr2.Nachfolger;
        falls Ptr2.Zahl<Pivot dann
           Ptr0:=Ptr1; 
           Ptr1:=Ptr1.Nachfolger;
           tausche(Ptr1,Ptr2)
     solange bis Ptr2=Rechts;
     tausche(Links,Ptr1)
     falls Ptr1<>Rechts dann Ptr1:=Ptr1.Nachfolger;
     QuickSort(Links,Ptr0);
     QuickSort(Ptr1,Rechts)
 ende

Der Nachteil dieses Verfahrens liegt darin, dass eine weitgehend sortierte Folge oder viele gleichartige Schlüsselwerte zu einem Worst-Case-ähnlichen Verhalten führen. Daher wählt man für verkettete Listen gern Sortieralgorithmen wie etwa Mergesort, die auch im Worst Case eine Zeitkomplexität von  \mathcal{O}(n \log (n)) besitzen. Andere dynamische Datenstrukturen wie balancierte Bäume (z. B. B-Bäume, AVL-Bäume) verteilen die Kosten des Sortierens auf die Einfügeoperationen, so dass nachträgliches Sortieren nicht notwendig ist.

Iteratives Quicksort[Bearbeiten]

Quicksort kann auch nicht-rekursiv mit Hilfe eines kleinen Stack oder Array implementiert werden. Hier eine einfache Variante mit zufälliger Auswahl des Pivotelements:

funktion quicksort_iterativ(links, rechts)
   zufall := random() // zufälliger Startwert
   wiederhole // äußere Schleife
      solange links < rechts wiederhole
         pivot := daten[random(links, rechts)] // Auswahl eines zufälligen Elements, das zwischen links und rechts liegt
         push (rechts) // rechten Teil später sortieren
         mitte := links - 1
         rechts := rechts + 1
         wiederhole // innere Schleife, teile Feld
            wiederhole mitte := mitte + 1 solange daten[mitte] < pivot
            wiederhole rechts := rechts - 1 solange daten[rechts] > pivot
            falls mitte >= rechts dann Abbruch innere Schleife
            tausche daten[mitte] mit daten[rechts]
         ende // Feld geteilt, linken Teil weitersortieren
      ende
      falls stapel leer dann Abbruch äußere Schleife // noch ein rechter Teil übrig ?
      links := rechts + 1
      pop (rechts) // jetzt rechten Teil sortieren
   ende
ende

Die Anweisung push legt dabei ein Element auf den Stack wo es mit pop wieder geholt wird. Die zufällige Wahl des Pivotelements sorgt dabei mit hoher Wahrscheinlichkeit für einen Average-Case. Die Größe des nötigen Stapelspeichers ist dabei mit ausreichender Sicherheit kleiner als 2·log2(n). Falls ein begrenzter Stapel trotzdem überläuft, so kann zum Sortieren des noch verbleibenden Teils einfach von vorne begonnen werden.

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  \mathcal{O}(n^2) 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 weiter zu sortieren.

QuickSort in funktionalen Sprachen[Bearbeiten]

In funktionalen Sprachen wie Haskell oder Erlang lässt sich QuickSort aufgrund mächtigerer Listenverarbeitung sehr einfach implementieren:

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (e:es) = quicksort [x | x <- es, x <= e] ++ [e] ++ quicksort [x | x <- es, x > e]

Dabei ist ++ der Verkettungsoperator für Listen; das Pattern (e:es) isoliert das erste Element der Liste und [x | x <- es, x <= e] ergibt alle Elemente der Liste es, die kleiner sind als das Pivotelement e.

Einzelnachweise[Bearbeiten]

  1.  C. A. R. Hoare: Quicksort. In: The Computer Journal. 5(1), 1962, S. 10-15, doi:10.1093/comjnl/5.1.10.
  2. Steven S. Skiena: The Algorithm Design Manual. Springer, 27 April 2011, ISBN 978-1-84800-069-8 (Zugriff am 18. Juli 2013).
  3. Eine Java Implementation einer stabilen in-place Variante von Quicksort
  4. Paul Hsieh: Sorting revisited.. www.azillionmonkeys.com. 2004. Abgerufen am 26. April 2010.
  5. David MacKay: Heapsort, Quicksort, and Entropy. www.aims.ac.za/~mackay. 1. Dezember 2005. Archiviert vom Original am 7. Juni 2007. Abgerufen am 26. April 2010.
  6.  Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed: Grundlagen von Datenstrukturen in C. 1. Auflage. International Thomson Publishing, 1994, ISBN 3-929821-00-1, S. 342.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]