QuickSort
Die folgende Prozedur sortiert ein Integer-Array, das der Routine als Parameter übergeben wird, mit dem QuickSort-Verfahren:
procedure QuickSort(var A: array of Integer); 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 Dec(Hi); if 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
procedure TForm1.Button1Click(Sender: TObject); 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.