Home » Tipps & Tricks » Algorithmen » Sortieren » QuickSort

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.