コムソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

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

目次 1 アルゴリズム 1.1 Javaによる実装例 1.2 動作例 2 改良版アルゴリズム

[編集] アルゴリズム

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

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.3 で割り、小数点以下を切り捨てた数を新たに間隔 h とする。
6. h<1 になるまで、2に戻り繰り返す。

[編集] Javaによる実装例

// int data[];
for (int h = data.length; h > 0;) {
    h /= 1.3;
    for (int i = 0; i + h < data.length; i++) {
        if (data[i + h] < data[i]) {
            final int temp = data[i + h];
            data[i + h] = data[i];
            data[i] = temp;
        }
    }
}

[編集] 動作例

動作例として

8 4 3 7 6 5 2 1

という数列を昇順に整列してみる。このとき n=8 だから h=8÷1.3≒6 であるので

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÷1.3 = 6÷1.3 ≒ 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

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 （整列終了）

[編集] 改良版アルゴリズム

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