|
Der Quicksort ist das am häufigsten verwendete Sortierverfahren, weil es sehr einfach zu implementieren ist. Er wurde 1960 von C.A.R. Hoare entwickelt und wurde seither von vielen Forschern untersucht.
Der große Vorteil besteht darin, daß er am Ort abläuft, und das für das sortieren von N Elementen im Durchschnitt nur N log N Operationen erforderlich sind, und daß er eine extrem kurze innere Schleife besitzt.
Der Nachteil besteht darin, daß er rekursiv und störanfällig ist und, daß er im ungünstigsten Fall N² Operationen benötigt.
Es gibt nun bereits viele verbesserte Varianten von Quicksort die schneller, besser oder auch effizienter arbeiten als der Quicksort von 1960. Es gilt jedoch zu beachten, daß bei jeder Veränderung einer bestehenden Variante eine Vielzahl von Effekten auftreten können, die nicht beabsichtigt waren. Wenn eine Variante entwickelt worden ist, die von solchen Effekten frei zu sein scheint wird diese meist als Bibliotheks- oder Standardsortierprogramm genutzt. Wenn man jedoch den Aufwand, um sicher zu sein, daß die Implementation von Quicksort nicht fehlerbehaftet ist, nicht investieren will, so ist Shellsort durchaus eine sichere Alternative, die bei geringem Aufwand für die Implementation recht effizient abläuft.
Das nachfolgende Programm ist die allgemeine Darstellung eines Quicksorts:
procedure quicksort(l,r:integer);
var i:integer;
begin
if r>l then
begin
i:=partition(l,r);
quicksort(l,i-l);
quicksort(i+l,r);
end
end;
Die Partition funktioniert wie folgt:
Beschreibung:
Das Feld wird nun von rechts nach links und von links nach rechts durchgegangen. Die am weitesten rechts befindliche Zahl 23 wird als das zerlegende Element gewählt. Wenn man nun von rechts nach links geht, wird immer nur dann unterbrochen, wenn ein Element kleiner ist als die 23, d.h. bei der Zahl 10. Wenn man von links nach rechts geht wird immer nur dann unterbrochen, wenn ein Element gefunden wird, das größer ist als die Zahl 23, d.h. die Zahl 52. Bei den Zahlen 10 und 52 bleiben nun die Zeiger stehen. Die beiden Zahlen werden vertauscht. Der Zeiger ist in der Darstellung der nach oben zeigende Pfeil.
In der zweiten Zeile wird nun bei der Zahl 10 und der Zahl 52 weitergegangen. Wenn man von rechts nach links geht, trifft man auf die Zahl 22, die kleiner ist als die 23. Von links nach rechts trifft man auf die Zahl 37, die größer ist als die Zahl 23, d.h. die beiden Zahlen werden vertauscht.
In der dritten Zeile fängt man nun wieder bei 22 und 37 an. Geht man von rechts nach links trifft man auf die Zahl 8, die kleiner ist als 23. Von links nach rechts trifft man auf die Zahl 5, die kleiner ist als 23, d.h. es wird weitergegangen bis zum 8er. Hier stoßen die beiden Zeiger zusammen.
Unser Feld ist getrennt. Man kann erkennen, daß alle Zahlen, die links von 23 stehen kleiner sind, und alle, die rechts von 23 stehen größer sind. Nun muß man das linke und das rechte Feld getrennt voneinander sortieren, und zwar genauso wie bis jetzt.
Beschreibung:
Hier ist unser auserwähltes Element die Zahl 8.
Nun geht man, wieder wie vorher, von rechts nach links, um ein Element, das kleiner als der 8er ist, zu finden. Hier sind wir gleich beim 5er angelangt. Der Zeiger bleibt auf dieser Position stehen.
Von links nach rechts sucht man ein Element, das größer ist als der 8er, nämlich gleich den 14er. Nun vertauscht man die beiden.
In der zweiten Zeile wird wieder vom 5er und vom 14er ausgegangen. Man sucht wieder ein kleineres und ein größeres Element als den 8er und tauscht sie aus, so lange, bis dieses Feld wieder geteilt ist. Man muß alle Teile sortieren, bis man sie sortiert zusammenhängen kann.
Ein Quicksort in Pascal würde wie folgt lauten:
procedure quicksort(l,r:integer);
var v,t,i,j:integer;
begin
if r>l then
begin
v:=a[r]; i:=l-1; j:=r;
repeat
repeat i:=i+1 until a[i]>=v;
repeat j:=j-1 until a[j] |
