●コムソート

※上記の広告は60日以上更新のない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)
名前:
コメント:


ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。