|
Beschreibung
. Das Verfahren arbeitet nach dem Divide & Conquer-Prinzip.
. Aus einer zu sortierenden Teilfolge wird ein Element ausgewählt.
. Die Folge wird so umsortiert, daß das ausgewählte Element an seine insgesamt (bezogen auf den Sortiervorgang der vollständigen Datenfolge) richtige endgültige Position zu liegen kommt.
. Nach dem Umordnen dürfen links vom ausgewählten Element nur mehr kleinere Elemente stehen und rechts nur mehr größere.
. Dann wird für die Folgen links und rechts vom ausgewählten Element das Verfahren rekursiv aufgerufen.
. Das korrekte Umordnen wird dadurch erreicht, daß von links her Elemente gesucht werden, die in die rechte Hälfte gehören, und von rechts her solche, die in die linke Hälfte gehören. Dann werden diese falsch plazierten Elemente vertauscht. Das Umordnen endet, wenn die beiden Suchvorgänge an der endgültigen Position des ausgewählten Elements zusammenstoßen.
Programmcode
procedure QuickSort ( var f : TArray; HighIndex : integer ) : string;
procedure rQuickSort ( links, rechts : integer);
// rekursiver Teil des QuickSorts
// Als Trennelement wird das jeweils mittlere Element der Teilfolge ausgewählt.
var i, j, x : integer;
begin
if links < rechts
then begin
i := links;
j := rechts;
x := f[(i+j) div 2]; // Wert des Trennelements
repeat
while f[i] < x do inc(i);
while f[j] > x do dec(j);
if i < j then swap (f[i], f[j]);
until i >= j;
rQuickSort (links, j-1 );
rQuickSort (j+1 , rechts);
end;
end; // rQuicksort
begin // QuickSort
rQuickSort (0, HighIndex);
end; // QuickSort
Aufwandsabschätzung
Aufwand:
. In jeder Ebene der Rekursion wird jedes Element betrachtet, d.h. n-Elemente.
. Die Rekursionstiefe hängt davon ab welches Element als Trennelement gewählt wurde. Im besten Fall wird immer genau das tatsächlich mittlere gewählt, dann ist die Rekursionstiege ld (n). Normalerweise wird das gewählte Trennelement nicht genau das mittlere sein, sodaß sich die Rekursionstiefe etwas verschlechtert: ~ 1,4 ld (n).
Daraus folgt der Aufwand .
worst-case-Aufwand:
Wenn zufällig immer das kleinste oder das größte Element als Trennelement auswählt wird, beträgt die Rekursionstiefe n/2 und somit der Aufwand .
Sortierdauer
|
