日本語ではコムソートともいう。comb=櫛のことであり、髪を櫛で梳くように一定の平行間隔を持った操作点で配列を整理していくことが由来。
バブルソートの改良版であり、実測は平均時間がほぼO(n log n)で安定と中々優秀。最良時間がO(n)でなくなったという面もあるものの、ぶっちゃけ誰も得しない性質だったので、なに、気にすることはない。安定ソートではない。
1980年発見、その後1991年に再発見されて現在の名前になったアルゴリズムであり、50~60年代生まれがザラなソート業界では割と新参者である。
原理
基本原理はバブルソートと同じで、2つの値を比較して大きい方が浮かんでいくというもの。
バブルソートのクソっぷりは、何と言っても値の前方向への移動効率がもの凄く悪いという点にある。そこで、バブルソートのように隣り合わせの値ではなく、比較交換する間隔を広く取れば、一ループに一回の移動でも大きくジャンプできるじゃないか、という発想がでてくる。渋滞解消のためにバイパスを通せまいかというわけである。
全体的な動きはシェルソートと挿入ソートの関係に似ており、最初は大きな間隔で、段々幅を狭めて繰り返し、最後はバブルソートそのものになる。もちろんバブルソートになった時点で遅くなる要素の排除は終わっており、これが足を引っ張るということはない(バブルソートは隣同士の入れ替えだけで済むなら遅くない)。
なお、一般にコームソートでは間隔の初期値を配列長/1.3の小数点切り捨て、以下ループ毎に1.3で割っていき、最後はバブルソートになると決まっている。これはコームソートの発案者が様々な配列でデータを取り、経験的に最良のものを選んだ結果だそうである。
性能検討
計算オーダーはクイックソートやマージソートに匹敵するかなりの高速ソート。実測でもこれらより幾らか遅い程度となる。とてもバブルソートの改良版とは思えない。
重要なのは交換型の内部ソートという点であり、これにより計算途中の余計なバッファを全く必要としないという特性を持つ。スピードも欲しいがメモリ使用量を抑えたいというケースにおいて有力な候補である。
関連項目
- 1
- 0pt
