|
コムソート（）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した〔"A Fast Easy Sort" , ''Byte'' Magazine, April 1991〕。 バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。 ==アルゴリズム== 挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。 # 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。 # i=0 とする。 # i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。 # i=i+1 とし、i+h>n となるまで3を繰り返す。 # hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。 # h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「コムソート」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Comb sort 」があります。 スポンサード リンク
|