コムソート(英: comb sort)やコームソートや櫛(くし)ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し[2][1]、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した[3]。 バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。 アルゴリズム[編集] 挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。 i=0 とする。 i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。 i=i+1 とし、i+h>n となるまで3を繰り返す。 hがすでに1になっている場合は入れ替えが発生
![コムソート - Wikipedia](https://cdn-ak-scissors.b.st-hatena.com/image/square/e51b9d5e128af681024394a34e6f9b23d3f95d94/height=288;version=1;width=512/https%3A%2F%2Fupload.wikimedia.org%2Fwikipedia%2Fcommons%2F4%2F46%2FComb_sort_demo.gif)