C++で実装するコムソート（Comb Sort）アルゴリズムの解説とサンプルコード

コムソート（Comb Sort）は、バブルソートやカクテルソートに似たソートアルゴリズムです。大きな特徴は、隣接する要素同士を比較するのではなく、一定間隔（ギャップ）だけ離れた要素同士を比較していく点にあります。

ギャップは [n/c] として定義されます。ここで n は要素数、c は縮小係数（シュリンクファクター）です。各反復処理が終わるたびにギャップを c で割り、切り捨てていきます。これを繰り返し、最終的にはギャップが1、つまり隣接する要素同士の比較になります。

入力：5 3 4 2 1
出力：1 2 3 4 5

コムソートの仕組み

コムソートでは、まず大きめのギャップで離れた要素同士を比較・交換します。これにより、配列の後ろ側にある小さな値（いわゆる「ウサギ」）や前側にある大きな値（「カメ」）を素早く移動させることができ、バブルソートの弱点を克服しています。

具体的な流れは以下の通りです。

1. 初期ギャップを要素数 n に設定します。
2. 各パスの前に、ギャップを gap × 10 / 1.3 で更新します（縮小係数は一般的に 1.3 が推奨されています）。
3. ギャップが 9 または 10 になった場合は 11 に設定します（これは経験的にソート効率を上げるための調整です）。
4. ギャップが 1 未満になった場合は 1 に設定します。
5. ギャップ分離れた要素同士を比較し、順序が逆なら交換します。交換が一度でも発生したらフラグを立てます。
6. ギャップが 1 になり、かつ交換が一切発生しなくなった時点でソート完了です。

C++による実装例

以下は、コムソートを C++ で実装したサンプルコードです。

#include <iostream>
using namespace std;

void combsort(int a[], int n) {
    int i, j, gap, swapped = 1;
    int temp;
    gap = n;
    while (gap > 1 || swapped == 1) {
        gap = gap * 10 / 1.3;   // ギャップを縮小
        if (gap == 9 || gap == 10) {
            gap = 11;           // 効率化のための特別な調整
        }
        if (gap < 1) {
            gap = 1;            // 最小ギャップは1
        }
        swapped = 0;
        for (i = 0, j = gap; j < n; i++, j++) {
            if (a[i] > a[j]) {  // 順序が逆なら交換
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                swapped = 1;
            }
        }
    }
}

int main() {
    int n, i;
    int arr[] = { 5, 3, 4, 2, 1 };
    n = 5;
    combsort(arr, n);
    for (i = 0; i < n; i++) {
        cout << arr[i] << "\t";
    }
    return 0;
}

実行結果

1	2	3	4	5

計算量について

コムソートの平均計算量は O(n log n) 程度とされ、最悪の場合でもバブルソートの O(n²) よりも大幅に改善されることが多いです。ただし、理論上の最悪計算量は O(n²) のままなので、厳密な性能保証が必要な場面ではクイックソートなどの他のアルゴリズムとの使い分けを検討するとよいでしょう。

実装がシンプルで追加のメモリ領域がほぼ不要なため、組み込みシステムなどリソースが限られた環境でも扱いやすいソート手法といえます。