コームソート単語

コームソート

コームソートはソートアルゴリズムの一種。

日本語ではコムソートともいう。comb=櫛のことであり、を櫛で梳くように一定の行間隔を持った操作点で配列を整理していくことが由来。

バブルソート良版であり、実測は均時間がほぼO(n log n)で安定と中々優秀。最良時間がO(n)でなくなったという面もあるものの、ぶっちゃけも得しない性質だったので、なに、気にすることはない。安定ソートではない。

1980年発見、その後1991年に再発見されて現在の名前になったアルゴリズムであり、50~60年代生まれがザラソート業界では割と新参者である。

原理

基本原理はバブルソートと同じで、2つの値を較して大きい方が浮かんでいくというもの。

バブルソートクソっぷりは、何と言っても値の前方向への移動効率がもの凄く悪いという点にある。そこで、バブルソートのように隣り合わせの値ではなく、較交換する間隔を広く取れば、一ループに一回の移動でも大きくジャンプできるじゃないか、という発想がでてくる。渋滞解消のためにバイパスを通せまいかというわけである。

全体的な動きはシェルソート挿入ソートの関係に似ており、最初は大きな間隔で、段々幅を狭めて繰り返し、最後はバブルソートそのものになる。もちろんバブルソートになった時点で遅くなる要素の排除は終わっており、これが足を引っるということはない(バブルソートは隣同士の入れ替えだけで済むなら遅くない)。

なお、一般にコームソートでは間隔の初期値を配列長/1.3の小数点切り捨て、以下ループ毎に1.3で割っていき、最後はバブルソートになると決まっている。これはコームソートの発案者が様々な配列データを取り、経験的に最良のものを選んだ結果だそうである。

性能検討

計算オーダーはクイックソートマージソートに匹敵するかなりの高速ソート。実測でもこれらより幾らか遅い程度となる。とてもバブルソート良版とは思えない

重要なのは交換の内部ソートという点であり、これにより計算途中の余計なバッファを全く必要としないという特性を持つ。スピードも欲しいがメモリ使用量を抑えたいというケースにおいて有補である。

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%82%B3%E3%83%BC%E3%83%A0%E3%82%BD%E3%83%BC%E3%83%88

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

コームソート

まだ掲示板に書き込みがありません…以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • コームソートについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!