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