コムソート
クラスソート
データ構造配列
最悪計算時間 Ω ( n 2 ) {\displaystyle \Omega (n^{2})} [1]
最良計算時間 O ( n ) {\displaystyle O(n)}
平均計算時間 Ω ( n 2 / 2 p ) {\displaystyle \Omega (n^{2}/2^{p})} , p は増加数[1]
最悪空間計算量 O ( 1 ) {\displaystyle O(1)}

コムソート（英: 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になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。

h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。

Javaによる実装例public static void combSort(int[] data) { int h = data.length * 10 / 13; while (true) { int swaps = 0; for (int i = 0; i + h < data.length; ++i) { if (data[i] > data[i + h]) { swap(data, i, i + h); ++swaps; } } if (h == 1) { if (swaps == 0) { break; } } else { h = h * 10 / 13; } }}private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t;}
C言語による実装例void comb_sort(int* array, int size) { int h = size; bool is_swapped = false; while (h > 1 |。is_swapped) { if (h > 1) { h = (h * 10) / 13; } is_swapped = false; for (int i = 0; i < size - h; ++i) { if (array[i] > array[i + h]) { // swap int temp = array[i]; array[i] = array[i + h]; array[i + h] = temp; is_swapped = true; } } }}
動作例

動作例として8 4 3 7 6 5 2 1

という数列を昇順に整列してみる。このとき n=8 だから h=8÷1.3≒6 から始める。8と2、4と1を比較して2回交換を行う。8 4 3 7 6 5 2 12 4 3 7 6 5 8 12 1 3 7 6 5 8 4

次は h = 6÷1.3 ≒ 4。2と6、1と5のように比較してゆき、7と4のみが交換される。2 1 3 7 6 5 8 42 1 3 4 6 5 8 7

以下 h は 3 → 2 → 1 の順に減っていくので

h=3：交換なし2 1 3 4 6 5 8 7

h=2：交換なし2 1 3 4 6 5 8 7

h=1：交換3回2 1 3 4 6 5 8 71 2 3 4 6 5 8 71 2 3 4 5 6 8 71 2 3 4 5 6 7 8

この例では6回の交換で整列が終了した。
改良版アルゴリズム

h=9,10となったとき、強制的にh=11とすることで高速化したアルゴリズムを、Comb sort 11と呼ぶ。

hが9→6→4→3→2→1や10→7→5→3→2→1と遷移するよりも、11→8→6→4→3→2→1と遷移する方がうまく櫛が梳けるためである。
参照^ a b c Brejova, B. (September 2001). “Analyzing variants of Shellsort”. Information Processing Letters 79 (5): 223?227. doi:10.1016/S0020-0190(00)00223-4. 
^ W?odzimierz Dobosiewicz (1980). “An efficient variation of bubble sort”. Information Processing Letters 11: 5-6. doi:10.1016/0020-0190(80)90022-8. 
^ ⇒"A Fast Easy Sort", Byte Magazine, April 1991

表

話

編

歴
ソート
理論

計算複雑性理論

ランダウの記号

全順序

リスト

安定性

ソーティングネットワーク

比較ソート（英語版）

整数ソート（英語版）

交換ソート

バブルソート

シェーカーソート

奇偶転置ソート

コムソート

ノームソート

クイックソート

選択ソート

選択ソート

ヒープソート

スムースソート

デカルト木ソート

トーナメントソート

挿入ソート

挿入ソート

シェルソート

ツリーソート

図書館ソート

ペイシェンスソート

マージソート

マージソート

多層マージソート