コムソート

コムソート（Comb Sort）とは

コムソートは、1980年にWłodzimierz Dobosiewicz氏によって発表され、1991年にStephen Lacey氏とRichard Box氏によって再発見され、その際にコムソートと名付けられました。このソートアルゴリズムは、バブルソートの改良版として知られています。内部ソートに分類されますが、安定ソートではありません。

特徴

コムソートの大きな特徴は、その実行速度です。平均計算時間はほぼO(n log n)に達し、バブルソートと比較して大幅に高速化されています。これは、要素間の比較を行う間隔を徐々に狭めていくという、シェルソートと同様の改良アプローチによるものです。

アルゴリズムの詳細

コムソートのアルゴリズムは、以下のステップで構成されます。

1. 初期間隔の設定: ソート対象の数列の要素数 n を1.3で割り、小数点以下を切り捨てた値を初期の間隔 h とします。
2. 比較と交換: 数列のi番目の要素とi+h番目の要素を比較します。もしi+h番目の要素の方が小さければ、それらの要素を交換します。
3. 間隔の更新: 上記の比較と交換の操作を、i+hが数列の要素数 n を超えるまで繰り返します。
4. 間隔の縮小: 間隔 h を再び1.3で割り、小数点以下を切り捨てた値を新たな間隔 h とします。
5. 繰り返し: 間隔 h が1になるまで、ステップ2から4を繰り返します。間隔 h が1になった場合は、交換が発生しなくなるまでステップ2と3を繰り返します。

アルゴリズムの具体例

例として、次の数列を昇順にソートしてみましょう。


8 4 3 7 6 5 2 1


1. 初期設定: この数列の要素数 n は8なので、初期の間隔 h は 8 / 1.3 ≒ 6 となります。
2. 間隔h=6: 8と2、4と1を比較し、交換を行います。

8 4 3 7 6 5 2 1
2 4 3 7 6 5 8 1
2 1 3 7 6 5 8 4

3. 間隔h=4: 次に、間隔 h は 6 / 1.3 ≒ 4 になります。2と6、1と5、3と8、7と4を比較します。7と4のみ交換が発生します。

2 1 3 7 6 5 8 4
2 1 3 4 6 5 8 7

4. 間隔h=3, 2, 1: 同様の操作を間隔 h が 3, 2, 1 となるまで繰り返します。h=3とh=2では交換は発生しません。

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回の交換で数列が昇順にソートされました。

改良版アルゴリズム：Comb sort 11

コムソートのさらなる高速化のために、「Comb sort 11」と呼ばれる改良版アルゴリズムも存在します。このアルゴリズムでは、間隔 h が9または10になった場合、強制的にhを11に設定します。これは、hが9→6→4→3→2→1や10→7→5→3→2→1と遷移するよりも、11→8→6→4→3→2→1と遷移する方が、より効率的に数列を「梳く」ことができるためです。

まとめ

コムソートは、バブルソートの欠点を克服し、より高速なソートを実現するアルゴリズムです。その単純さと効率性から、様々な場面で利用されています。Comb sort 11のような改良版も存在し、さらなる高速化への探求も進んでいます。

もう一度検索