●コムソート

情報

作者名：ゆちボン
引用元：なでしこプログラム掲示板「なでしこでソートプログラム集」
解説引用元：http://ja.wikipedia.org/wiki/コムソート
リンク：●バブルソート、●双方向バブルソート、●おいこみソート

概要

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

---