QuickSort関数

Delphi(Win32)

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;
スポンサーリンク
スポンサーリンク

注意

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

スポンサーリンク
管理人

1983年生まれのえんじにゃー🐈
趣味はエレキギターなど。作曲したい。
WoWs/プリコネ/デレステ
記事に関する質問はお気軽にどうぞ。

たかおファン(surface0)をフォローする
たかおファン(surface0)をフォローする
Rain or Shine

コメント

タイトルとURLをコピーしました