「●コムソート」の編集履歴(バックアップ)一覧はこちら
「●コムソート」(2008/10/14 (火) 20:01:06) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*情報
作者名:ゆちボン
引用元:[[なでしこプログラム掲示板「なでしこでソートプログラム集」>http://www.himanavi.net/cgi/nade-bbs/cbbs.cgi?mode=al2&namber=940&rev=&no=0]]
解説引用元:[[http://ja.wikipedia.org/wiki/コムソート>http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88]]
リンク:[[●バブルソート]]、[[●双方向バブルソート]]、[[●おいこみソート]]
*概要
コムソート(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)
#comment()
----
*情報
作者名:ゆちボン
引用元:[[なでしこプログラム掲示板「なでしこでソートプログラム集」>http://www.himanavi.net/cgi/nade-bbs/cbbs.cgi?mode=al2&namber=940&rev=&no=0]]
解説引用元:[[http://ja.wikipedia.org/wiki/コムソート>http://ja.wikipedia.org/wiki/%E3%82%B3%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88]]
リンク:[[●バブルソート]]、[[●双方向バブルソート]]、[[●おいこみソート]]
*概要
コムソート(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)
#comment()
----