Logo: Titelseite, Fragezeichen: Hilfe, Liste: Externer Navigator, Pfeil: Nächste Seite

Quicksort Animation


Methode

Das Verfahren wurde 1962 von C.A.R. Hoare veröffentlicht und erhielt den namen Quicksort, weil es erfahrungsgemäß eines der schnellsten, wenn nicht das schnellste interne Sortier - verfahren ist.
Um eine Folge F = k1,..., kN von N Schlüsseln nach aufsteigenden Werten zu sortieren, wählen wir ein beliebiges Element k aus {k1,..., kN} und benutzen es als Angelpunkt, genannt Pivotelement, für eine Aufteilung der Folge ohne k in zwei Teilfolgen F1 und F2. F1 besteht nur aus Elementen von F, die kleiner oder gleich k sind, F2 nur aus Elementen von F, die größer oder gleich k sind. Ist F1 eine Folge mit i-1 Elementen und F eine Folge mit N- Elementen, so ist i die endgültige Position des Pivotelements k. Also kann man das Sortierproblem dadurch lösen, daß man F1 und F2 rekursiv auf dieselbe Weise sortiert und die Ergebnisse in offensichtlicher Weise zusammensetzt. Zuerst kommt die durch Sortieren von F1 entstandene Folge, dann das Pivotelement k (an Position i) und dann die durch Sortieren von F entstandene Folge.

Analyse

Wir schätzen zunächst die im schlechtesten Fall auszuführende Anzahl von Schlüsselvergleichen sowie die Anzahl der Bewegungen ab. Zur aufteilung eines Feldes der Länge N werden die Schlüssel aller Elemente im aufzuteilenden Bereich je einmal mit dem Pivotelement verglichen. im ungünstigsten Fall wechseln dabei alle Elemente je einmal ihren Platz. Die im ungüstigsten Fall auszuführende Anzahl von Schlüsselvergleichen und Bewegungen hängt damit stark von der Anzahl der Aufteilungsschritte und damit von der Zahl der iniitierten rekursiven Aufrufe ab. Ist das Pivotelement das Element mit kleinstem oder größtem Schlüssel, ist eine der beiden durch Aufteilung entstehenden Folgen jeweils leer und die andere hat jeweils ein Element weniger als die Ausgangsfolge. Dieser Fall tritt z.B. für eine bereits aufsteigend sortierte Folge von Schlüssel ein.
Zum Sortieren von N Elemente mit Quicksort gilt für die maximale Anzahl Cmax(N) von auszuführenden Schlüsselvergleichen
Cmax(N)>=N+(N-1)+(N-2)+...+1=O(N²).
Für die maximale Anzahl von Bewegungen gilt:
Mmax(N)=O(N²).
Quicksort benötigt im schlechtesten Fall also quadratische Schrittzahl. Im günstigsten Fall haben die durch Aufteilung entstehenden Teilfolge stets etwa gleiche Länge. Dann hat der Baum der initiierten rekursiven Aufrufe die minimale Höhe. Zur Aufteilung aller Folgen auf einem Niveau werden O(N) Schlüsselvergleiche durchgeführt. Da der Aufrufbaum im günstigsten Fall nur die Höhe log N hat, folgt: Cmin(N)=O(N log N).
Die mittlere Laufzeit von Quicksort ist nicht viel schlechter als die Laufzeit im günstigsten Fall, also benötigt auch O(N log N).

Animation

Um ein besseres Verständnis zu bekommen, können Sie den Ablauf des Algorithmus an der Animation verfolgen. Quicksort animiert

Logo: Abteilungsseite, Pfeile: Seitenanfang, nächste Seite

Letzte Änderung 10. Februar 1998 © Copyright 1998 Andreea Barbu