Dagmar de Haan, Freiherr-vom-Stein-Gymnasium Oberhausen
Inhalt:
4. Leistung und Probleme des Verfahrens
Quicksort wurde 1960 von C.A.R. Hoare erfunden und gilt als schnellstes internes Sortierverfahren. Es ist ein rekursives Verfahren und beruht auf dem Prinzip des Austauschens über große Distanz.
Seine Schnelligkeit verdankt es dem Umstand, dass keine Unterteilung in einen sortierten und einen unsortierten Teil vorgenommen wird. Durch Zerlegung wird das gesamt Feld in immer kleinere Teile geteilt, bis schließlich die Teilstücke nur noch ein Element enthalten. Durch gleichzeitiges Austauschen ist das Feld am Ende geordnet. Trotz vielfacher Versuche, Quicksort verbessern zu wollen, hat sich gezeigt, dass der ursprüngliche Algorithmus schon so ausgewogen ist, dass eine Verbesserung in einem Teil zu einer Verschlechterung in einem anderen Teil führt.
Aus dem zu sortierenden Feld wird ein geeignetes Vergleichselement (z.B. das
mittlere) gewählt. Ein von links kommender Zeiger durchsucht den linken Teil des
Feldes nach Elementen größer oder gleich dem Vergleichselement, ein von rechts
kommender Zeiger durchsucht den rechten Teil nach Elementen kleiner oder gleich
dem Vergleichselement. Die beiden gefundenen Elemente werden vertauscht
(Tauschen über große Distanz). Wichtig ist dabeim, dass auch das
Vergleichselement getauscht wird, da ansonsten nicht gewährleistet ist, dass
Quicksort richtig sortiert. Die beiden Zeiger setzen ihre Suche fort, bis sie
sich treffen bzw. "überholen". Das Feld ist jetzt schon ansatzweise sortiert,
und zwar in einen Teil mit Elementen kleiner-gleich dem Vergleichselement und
einen Teil mit Elementen größer-gleich dem Vergleichselement. Das
Vergleichselement ist an seiner endgültigen Position. Diese beiden entstandenen
Teile werden nach dem gleichen Verfahren (Divide-and-conquer-Verfahren) rekursiv
(d.h. der Algorithmus ruft sich selber auf) in immer kleinere Teilfelder
zerlegt, bis am Ende alle Elemente in einer sortierten Reihenfolge
stehen.
procedure quicksort (links, rechts: Integer);
var i, j: Integer; x, w: Element;
begin
If rechts > links Then (* mehr als ein Element enthalten? *)
begin
x := A[(links + rechts) div 2]; (* Vergleichselement festlegen *)
i := links;
j := rechts;
repeat
while A[i] < x do i := i + 1; (* Bewegung des linken Zeigers *)
while A[j] > x do j := j – 1; (* Bewegung des rechten Zeigers *)
If i <= j Then
begin
w := A[i]; (* Vertauschen von A[i] und A[j] *)
A[i] := A[j];
A[j] := w;
i := i + 1; (* Zeigerbewegung *)
j := j – 1;
end;
until i > j;
quicksort (links, j);
quicksort (i, rechts);
end;
end;
| Unsortierte Zahlen: | 28 58 23 17 91 11 80 54 |
| Vergleichselement wählen | x=A[3]=23; |
| Grenzen festlegen: | i=1, j=8 28 58 23 17 91 11 80 54 i j |
| Feld durchsuchen: |
i=A[1]=28, j=A[6]=11 28 58 23 17 91 11 80 54 i j |
| A[1] und A[6] vertauschen, i und j eine Position weiter schieben: |
i=A[2]=58, j=A[5]=91
11 58 23 17 91 28 80 54
i j |
| Feld durchsuchen: |
i=A[2]=58, j=A[4]=17
11 58 23 17 91 28 80 54
i j |
| A[2] und A[4] vertauschen, i und j eine Position weiter schieben: |
i=A[3]=23, j=A[3]=23
11 17 23 58 91 28 80 54
ij |
| A[3] mit sich selbst vertauschen, i und j eine Position weiter schieben: |
i=A[4]=58,
j=A[2]=17
11 17 23 58 91 28 80 54
j i |
| Teilfelder 11 17 und 58 91 28 80 54 sortieren: | 11 17 23 58 91 28 80 54
j i |
4. Leistung und Probleme des Verfahrens
Leistung:
Die Vorteile von Quicksort sind, dass es eine sehr kurze innere Schleife (Bewegung der Zeiger, Vergleich mit Vergleichselement) besitzt und dass es am Ort ("in-place") abläuft, d.h. nur einen kleinen Hilfsstapel verwendet.
Im Mittel benötigt Quicksort für das Sortieren von N Elementen nur 2N*ln(N) Vergleiche. Der optimale Fall für Sortieren mit Quicksort ist, wenn jede Zerlegung das Feld genau halbieren würde, es würden dann N*lg(N) Vergleiche benötigt. Da 2N*ln(N) ~ 1,38*N*lg(N) gilt, ist die durchschnittliche Zahl der Vergleiche um etwa 38% größer als im Idealfall.
Probleme:
Der große Nachteil des Algorithmus ist, dass er extrem störanfällig ist. Schon kleine Eingriffe oder Fehler bei der Implementation können das Verfahren stark verlangsamen oder sogar in eine Endlosschleife verwandeln.
Ein weiterer Nachteil ist, dass Quicksort für eine große Anzahl zu sortierender Elemente zwar sehr schnell ist, seine Leistung bei kleinem N, wie bei allen höheren Sortiermethoden, schwach ist.
Im schlimmsten Fall, wenn immer das größte Element als Vergleichselement gewählt wird, benötigt Quicksort zum Sortieren von N Elementen N² Operationen, Quicksort wird zum Slowsort.
Geeignetes Vergleichselement:
Da die Schwachen von Quicksort anscheinend mit der Wahl des Vergleichselementes zusammen hängen, ist es von besonderer Bedeutung, ein geeignetes Element zum Vergleichen zu finden.
Hoare hat den Vorschlag gemacht, entweder eine willkürliche Wahl (Randomize) zu treffen oder das mittlere von drei Elementen zu wählen (A[links],A[rechts],A[(links+rechts) div 2]).
Die durchschnittliche Leistung wird durch dieses Vorgehen nicht beeinflußt, die Leistung im schlimmsten Fall aber erheblich verbessert.
In der Regel wird, der Einfachheit halber und da die Leistung im Mittel etwas
besser ist, das mittlere Element als Vergleichselement gewählt
(A[(links+rechts) div 2]).
Da einige ältere Programmiersprachen nicht in der Lage sind, mit Rekursion zu arbeiten, hat man für Quicksort einen Algorithmus ohne Rekursion entwickelt. Da jede Zerlegung zwei weitere Zerlegungen nach sich zieht, aber immer nur ein Teilstück bearbeitet werden kann, benötigt man als Hilfsmittel zur Speicherung des nicht bearbeiteten Teilstückes einen Stapel (Stack). Dadurch das immer das größte Teilstück zuerst im Stapel abgelegt wird und das kleinste Teilstück nicht in den Stapel kommt, wird gewährleistet, dass der Stapel nur für ungefähr lg(N) Element Platz haben muß (bei der rekursiven Implementation erreicht der Stapel im schlimmsten Fall die Größe N ).
Implementation ohne Rekursion:
procedure quicksort;
var i, j, links, rechts: Integer; x, w: Element;
begin
links := 1;
rechts := N;
stackinit;
push (links);
push (rechts);
repeat
If rechts > links then
begin
x := A[(links + rechts) div 2];
i := links;
j := rechts;
repeat
while A[i] < x do i := i + 1;
while A[j] > x do j := j – 1;
if i <= j then
begin
w := A[i];
A[i] := A[j];
A[j] := w;
i := i + 1;
j := j – 1;
end
until i > j;
if (i – links) > (rechts - i) then
begin
push (links);
push (i - 1);
links := i + 1;
end
else begin
push (i + 1);
push (rechts);
rechts := i –1;
end
else begin
r := pop;
l := pop;
end
until stackempty
end;