コムソートのソースを表示

{{Infobox algorithm
|class=[[ソート]]
|image=[[File:comb_sort_demo.gif|Visualisation of comb sort]]
|data=[[配列]]
|time=<math>\Omega(n^2)</math><ref name=BB/>
|average-time=<math>\Omega(n^2/2^p)</math>, {{math|''p''}} は増加数<ref name=BB/>
|best-time=<math>O(n)</math>
|space=<math>O(1)</math>
|optimal=
}}

'''コムソート'''（{{lang-en-short|comb sort}}）や'''コームソート'''や'''櫛（くし）ソート'''は、[[ソート]]の[[アルゴリズム]]の一つ。1980年に Włodzimierz Dobosiewicz が発表し<ref>{{Cite journal
 |title=An efficient variation of bubble sort
 |author=Włodzimierz Dobosiewicz
 |journal=Information Processing Letters
 |volume=11
 |year=1980
 |pages=5-6
 |doi=10.1016/0020-0190(80)90022-8
}}</ref><ref name="BB">{{Cite journal
 | doi = 10.1016/S0020-0190(00)00223-4
 | title = Analyzing variants of Shellsort
 | journal = Information Processing Letters
 | volume = 79
 | issue = 5
 | pages = 223–227
 | year=2001
 | month=September
 | last1 = Brejová
 | first1 = B. 
}}</ref>、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した<ref>[http://cs.clackamas.cc.or.us/molatore/cs260Spr03/combsort.htm "A Fast Easy Sort"], [[Byte Magazine|''Byte'' Magazine]], April 1991</ref>。

[[バブルソート]]の改良版。内部ソートだが、[[安定ソート]]ではない。実行速度は、ほぼ[[ランダウの記号|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による実装例 ===
<syntaxhighlight lang="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;
}
</syntaxhighlight>

===C言語による実装例===
<syntaxhighlight lang="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;
            }
        }
    }
}
</syntaxhighlight>

=== 動作例 ===
動作例として
: 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と遷移する方がうまく櫛が梳けるためである。

== 参照 ==
{{reflist}}

{{ソート}}
[[Category:ソート|こむそおと]]