コムソート(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;