コムソート

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

コムソート（英: comb sort）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し^[2][1]、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した^[3]。

バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。

挿入ソートをシェルソートに改良したときと同様の改良を施す。適当な間隔で整列後、間隔を少しずつ狭めて整列していく。

1. 総数 n を 1.3 で割り、小数点以下を切り捨てた数を間隔 h とする。
2. i=0 とする。
3. i 番目と i+h 番目を比べ、i+h 番目が小さい場合入れ替える。
4. i=i+1 とし、i+h>n となるまで3を繰り返す。
5. hがすでに1になっている場合は入れ替えが発生しなくなるまで上の操作を繰り返す。
6. h を 1.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とし、操作を繰り返す。

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;
}

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 1

2 4 3 7 6 5 8 1

2 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 4

2 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 7

1 2 3 4 6 5 8 7

1 2 3 4 5 6 8 7

1 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と遷移する方がうまく櫛が梳けるためである。

表 話 編 歴 ソート
理論	計算複雑性理論 ランダウの記号 全順序 リスト 安定性 ソーティングネットワーク 比較ソート（英語版） 整数ソート（英語版）
交換ソート	バブルソート シェーカーソート 奇偶転置ソート コムソート ノームソート クイックソート
選択ソート	選択ソート ヒープソート スムースソート デカルト木ソート トーナメントソート
挿入ソート	挿入ソート シェルソート ツリーソート 図書館ソート ペイシェンスソート
マージソート	マージソート 多層マージソート ストランドソート
非比較ソート	基数ソート バケットソート 計数ソート プロキシマップソート 鳩の巣ソート バーストソート ビーズソート
並行ソート	バイトニックソート バッチャー奇偶マージソート シェアソート
混成ソート	ティムソート イントロソート Jソート アンシャッフルソート（英語版）
その他	トポロジカルソート パンケーキソート スパゲティソート
非効率的/ ユーモラスソート	ボゴソート ストゥージソート スリープソート エラーソート
カテゴリ