コムソート

コムソート

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

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

バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼ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 21

243 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 76 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 13 4 6 5 8 7

1 2 3 4 658 7

1 2 3 4 5 6 87

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