Quicksort

Quicksort (von engl. quick – schnell, 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).

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

Prinzip

Zunächst wird die zu sortierende Liste in zwei Teillisten umsortiert. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus, das die Grenze zwischen den beiden Teillisten festlegt. Alle Elemente die kleiner als das Pivotelement sind, kommen in die linke, untere Teilliste und alle die größer sind, in die rechte, obere Teilliste. Die Längen der Teillisten werden also nicht schon vorher festgelegt, sondern ergeben sich aus der Wahl des Pivotelements. 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.

Am Ende der Aufteilung sind die beiden Teillisten zueinander bereits sortiert: ein Element aus der unteren Teilliste ist immer kleiner gleich einem Element aus der oberen Teilliste. 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 unteren und auf der oberen Teilliste ausgeführt. Diese Selbstaufrufe werden als Rekursion bezeichnet. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion, d. h. für diese Teilliste wird Quicksort nicht mehr aufgerufen.

Das Verfahren muss sicherstellen, dass eine Teilliste 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.

Allgemeine Implementierung

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" das zu sortierende Feld ist. Dabei hat beim ersten Aufruf von quicksort (oberste Rekursionsebene) der Parameter links den Wert 0 (Index des ersten Feld-Elements) und rechts den Wert n (Index des letzten Feld-Elements). Die Bezeichnungen links und rechts beziehen sich auf die Anordnung des Felds: daten[0], daten[1],... , daten[n].

 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 oder gleich dem Pivotelement ist
         wiederhole solange daten[i] < pivot und i < rechts
             i := i + 1  
         ende 

         // Suche von rechts ein Element, welches kleiner oder gleich dem Pivotelement ist
         wiederhole solange pivot < daten[j] und j > links
             j := j - 1 
         ende  

         falls i <= j dann tausche daten[i] mit daten[j], erhoehe i um 1, verkleinere j um 1

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

     // Tausche Pivotelement (daten[rechts]) mit neuer endgültigen Position (daten[i])

     tausche daten[i] mit daten[rechts]

     // 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 oder gleich dem Pivotelement ist. Entsprechend wird vom Ende der Liste beginnend ein Element kleiner oder gleich dem 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.

Implementierung in Pascal und Delphi

Hier ist eine funktionierende Implementation in Delphi (Pascal) mit einigen Kommentaren zu sehen, welche ein Integer-Array sortiert. Man kann das Integer hier auch beliebig durch den Typ Real oder Double ersetzen.

procedure QSort(var A: array of integer; iLo, iHi: integer);
var Lo, Hi, Mid, T: Integer;
begin
  Lo := iLo; Hi := iHi;
  Mid := A[(Lo + Hi) div 2]; {Das Array in der Mitte teilen}
  repeat
    while A[Lo] < Mid do Inc(Lo);
    while A[Hi] > Mid do Dec(Hi);
    if Lo <= Hi then begin 
      T := A[Lo]; A[Lo] := A[Hi]; A[Hi] := T; 
      Inc(Lo); Dec(Hi); 
    end;
  until Lo > Hi;
  if Hi > iLo then QSort(A, iLo, Hi); {Sortieren des rechten Teils}    
  if Lo < iHi then QSort(A, Lo, iHi); {Sortieren des linken Teils}  
end;

begin
  QSort(A, Low(A), High(A)); {Erster Aufruf mit gesamten Array}
  {Implementierung von Markus Gronotte in Pascal}
end;

Beispiel `teile(links, rechts)`

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

Komplettes Beispiel

In diesem Beispiel soll der Quicksortalgorithmus die Buchstabenfolge "Quicksort" sortieren

Quicksort

^ ^^ g kP

Quicksort
 ^     ^^
 g     kP

Qricksout
 ^     ^^
 g     kP

Qricksout
      ^^^
      kgP

Qricksotu
      ^^^
      kPg

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

Qrickso|t|u

^ ^^ g kP

Qrickso|t|u
^   ^ ^  
g   k P

kricQso|t|u
^   ^ ^  
g   k P

kricQso|t|u
 ^ ^  ^  
 g k  P

kcirQso|t|u
 ^ ^  ^  
 g k  P

kcirQso|t|u
  ^^  ^  
  kg  P

kcioQsr|t|u
  ^^  ^  
  kP  g

links:rechts

kci|o|Qsr|t|u
  ^|^|  ^| | 
  k|P|  g| |

    :
kci|o| Qsr|t|u

^ ^^| |^ ^^| | g kP| |g kP| |

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

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

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

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

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

cik|o| Qrs|t|u

cikoQrstu

"Bitte in den nächsten 2 Stunden nicht verändern ich mache gerade noch zusatzkommentare in den zwischenschritten."

Kenngrößen

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^{2}$ .

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.

Speicherplatz

Quicksort ist ein in-Place-Verfahren: Es kopiert die Elemente der zu sortierenden Liste nicht in zusätzlichen Speicherplatz, sondern vertauscht sie nur innerhalb der Liste. Das Verfahren benötigt für jede Rekursionsebene einen konstanten 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 O(log(n)), wird auch nur eine Stapelgröße von 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 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 bzw. die Wahrscheinlichkeit des Auftretens zu vermindern^[2]:

Endrekursionsbeseitigung (siehe nachfolgenden Pseudocode)
eine ausgewogenere Wahl des Pivotelements (Median von Drei)
Wahl eines zufälligen Pivotelements, was systematische Probleme durch die ursprüngliche Anordnung der Elemente vermeidet
Vermeidung von Teilisten 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

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 weiter zu sortieren.

Siehe auch: Introsort

Weitere Sortierverfahren

Siehe auch: Sortierverfahren

Literatur

↑ C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962)
↑ 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.

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

Weblinks

[Hoare-1] C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962)

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

[1]

[2]

Quicksort

Inhaltsverzeichnis

Prinzip

Allgemeine Implementierung

Implementierung in Pascal und Delphi

Beispiel `teile(links, rechts)`

Komplettes Beispiel

Kenngrößen

Laufzeit

Speicherplatz

Varianten

Weitere Sortierverfahren

Literatur

Weblinks

Navigationsmenü

Quicksort

Prinzip

Allgemeine Implementierung

Implementierung in Pascal und Delphi

Beispiel teile(links, rechts)

Komplettes Beispiel

Kenngrößen

Laufzeit

Speicherplatz

Varianten

Weitere Sortierverfahren

Literatur

Weblinks

Navigationsmenü

Suche

Beispiel `teile(links, rechts)`