コムソート(Comb Sort)アルゴリズム ～Delphiソースコード集

検索：

コムソート(Comb Sort)アルゴリズム ～Delphiソースコード集

コムソート(Comb Sort)

コムソートは バブルソート を改良したアルゴリズムだそうです。
バブルソートは隣接する要素の比較を行いますが、コムソートは少し離れた要素を比較し、だんだん近い要素の比較を行うそうです。
処理速度もそこそこ速く、ソースコードもお手軽で、メモリを消費しない、再帰処理を行わないのでスタックも消費しません。
クイックソートやマージソートは処理速度が速いですが再帰処理を行うので要素数が多く（100万個程度？に）なると 「スタックオーバーフロー」エラーで停止するかもしれません。

コムソート(Comb Sort)

Integer型配列を小さい数字から昇順に並べ替えるコムソート関数 
uses System.Math;
procedure CombSort(a:TArray<Integer>);
  //二つの整数の値を入れ替える
  procedure SwapInt(var v1,v2:Integer);
  var sw:Integer;
  begin
    sw:=v1;
    v1:=v2;
    v2:=sw;
  end;
var between:Integer;//間隔
    i,l,h:integer;
begin
  l:=Low(a);
  h:=High(a);
  //初期の比較間隔
  between:=System.Math.Floor((h-l+1)/1.3);
  while between>0 do //比較間隔が0になったら終了
  begin
    i:=l;
    while h>=(i+between) do
    begin
      if a[i]>a[i+between] then
        SwapInt(a[i],a[i+between]);
      inc(i);
    end;
    //比較間隔を小さくする(1.3で割って切り捨て)
    between:=System.Math.Floor(between/1.3);
  end;
end;

使用例

procedure TForm1.Button1Click(Sender: TObject);
var a:TArray<Integer>;
    i:Integer;
    st:string;
begin
  SetLength(a,20);
  for i := Low(a) to High(a) do
  begin
    a[i]:=Random(100);
  end;

  st:='ソート前：';
  for i := Low(a) to High(a) do
    st:=st+Format('%3d',[a[i]]);
  Memo1.Lines.Add(st);

  CombSort(a);

  st:='ソート後：';
  for i := Low(a) to High(a) do
    st:=st+Format('%3d',[a[i]]);
  Memo1.Lines.Add(st);
  Memo1.Lines.Add('');
end;


（参考）構造体をコムソート(Comb Sort)で並び替える

TPoint型構造体配列を小さい数字から昇順に並べ替えるコムソート関数 
procedure CombSort(a:TArray<TPoint>);overload;
  //二つのTPoint構造体の値を入れ替える
  procedure SwapInt(var v1,v2:TPoint);
  var sw:TPoint;
  begin
    sw:=v1;
    v1:=v2;
    v2:=sw;
  end;
var between:Integer;//間隔
    i,l,h:integer;
begin
  l:=Low(a);
  h:=High(a);
  //初期の比較間隔
  between:=System.Math.Floor((h-l+1)/1.3);
  while between>0 do //比較間隔が0になったら終了
  begin
    i:=l;
    while h>=(i+between) do
    begin
      if (a[i].X>a[i+between].X) or
         (a[i].X=a[i+between].X) and (a[i].Y>a[i+between].Y) then
        SwapInt(a[i],a[i+between]);
      inc(i);
    end;
    //比較間隔を小さくする(1.3で割って切り捨て)
    between:=System.Math.Floor(between/1.3);
  end;
end;