情報
概要
コムソート(Comb Sort)は、ソートのアルゴリズムの一つ。コームソート、櫛(くし)ソートなどとも呼ばれる。
バブルソートの改良版。内部ソートだが、安定ソートではない。
安定:×
速度:ほぼ、o(n log n)
解説
ちなみに、コムソート11を使用してます。
コムソート11を使用しない場合は「※」がついている行を
コメントアウトしてくんさい。
※コムソート11とは?
gap=9,10となったとき、強制的にgap=11とすることで高速化したアルゴリズムを、Comb sort 11と呼ぶ。
gapが9→6→4→3→2→1や10→7→5→3→2→1と遷移するよりも、11→8→6→4→3→2→1と遷移する方がうまく櫛が梳けるためである。
サンプルプログラム
200回、テスト[回数-1]は乱数(200)
テストをコムソート。
テストをメモ記入。
おわり
//本体
●コムソート(Aを)
max=配列要素数(A)
'処理開始
gap=max
(gap>0)の間
gap=INT(gap/1.3)
もし、gap=9||gap=10なら、gap=11 '※
i=0
(i+gap<max)の間
もし、A[i+gap]<A[i]なら
tmp=A[i+gap]
A[i+gap]=A[i]
A[i]=tmp
i=i+1
Aで戻る。
- 掲載ありがとうございます!コムソート11の解説のところですが、本体のプログラムでは「h」ではなく「gap」という変数にしていますので、そちらにしていただけるとわかりやすいと思います。 -- ゆちボン (2008-10-14 17:07:02)
- 修正しましたー!ありがとうございますー! -- 管理人 (2008-10-14 20:01:06)
最終更新:2008年10月14日 20:01