●コムソート

情報

概要

安定：×
速度：ほぼ、o(n log n)

解説

※コムソート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)