コムソート

テンプレート:Infobox algorithm コムソート（comb sort）は、Stephen LaceyとRichard Boxが1991年4月に開発したソートのアルゴリズムの一つ。コームソート、櫛（くし）ソートなどとも呼ばれる。

バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼ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 とし、操作を繰り返す。

Javaによる実装例

public static final 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 final void swap(int[] a, int i, int j)
{
    final int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

C言語による実装例

void CombSort(int* array, int size){ 
	int h = size;
	bool is_swapped = false;
	int i, temp;
	
	while(h > 1 || is_swapped){
		if(h > 1){
			h = (h*10)/13;	
		}

		is_swapped = false;
		for(i = 0; i < size-h; ++i){
			if(array[i] > array[i+h]){
				//swap
				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と遷移する方がうまく櫛が梳けるためである。