QuickSort関数

C言語にはqsort()というクイックソートを行う関数が標準ライブラリに含まれているが、
Delphiにはそれに相当するものが見当たらないので自作してみた。

今回は汎用ではなくTIntegerDynArray専用とした。

procedure QuickSort(var Data: TIntegerDynArray);
procedure qSort(var Data: TIntegerDynArray;
                Lower, Upper: Integer);
var
  mid :Integer;
  tmp :Integer;
  i   :Integer;
  j   :Integer;
begin
  i := Lower;
  j := Upper;
  mid := Data[(Lower + Upper) div 2];
  repeat
    while Data[i] < mid do Inc(i);
    while Data[j] > mid do Dec(j);
    if i <= j then
    begin
      tmp := Data[i];
      Data[i] := Data[j];
      Data[j] := tmp;
      Inc(i);
      Dec(j);
    end;
  until i> j;

  if Lower < j then qSort(Data, Lower, j);
  if Upper > i then qSort(Data, i, Upper);
end;

begin
  qSort(Data, Low(Data), High(Data));
end;

注意

なにも工夫を凝らしていない再帰型の関数なので大量のデータを扱うとスタックオーバーフローを起こす可能性がある。その場合は自力でスタックする非再帰型の関数を用いる必要がある。