QuickSort |
|
| System | Win9x, WinNT, Win2000, WinXP, Vista, Win7 |
|---|---|
| Ab Delphi-Version | Delphi 4 |
| Letzte Änderung | 21.01.2012 |
Die folgende Prozedur sortiert ein Integer-Array, das der Routine als Parameter übergeben wird, mit dem QuickSort-Verfahren:
procedure Quick_Sort(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];
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 Quick_Sort(A, iLo, Hi);
if Lo < iHi then Quick_Sort(A, Lo, iHi);
end;
begin
Quick_Sort(A, Low(A), High(A));
end;
Beispiel der Anwendung
var
arr: array[0..100] of integer;
I: Integer;
begin
for I:=Low(arr) to High(arr) do
arr[I]:=Random(High(Integer));
QuickSort(arr);
end;
QuickSort ist ein instabliles Sortierverfahren, d.h., wenn zwei Einträge genau gleich sind, können sie vertauscht werden. Ist beispielsweise eine Kundenliste bereits nach Kundennummer sortiert und wird nun QuickSort angewendet um nach Namen zu sortieren, kann es beispielsweise passieren, dass Herr Müller mit Kundennummer 21 vor Herrn Müller mit Kundennummer 42 steht, aber Frau Mayer mit Kundennummer 522 vor Frau Mayer mit Kundennummer 311. Die Sortierung nach Kundennummer geht verloren.
QuickSort ist im besten, wie auch im durchschnittlichen Fall ein optimales Sortierverfahren, d.h. es lässt sich beweisen, dass es keinen Algorithmus gibt, der mehr als um einen konstanten Faktor schneller ist. Es gibt jedoch auch pathologische Fälle, in denen QuickSort recht langsam sortiert. Weitere Informationen finden sich z.B. in der Wikipedia.