コムソート（Comb Sort）とは？仕組み・計算量・C++実装例を解説

コムソートは、バブルソートの改良版として知られるソートアルゴリズムです。基本的な考え方はバブルソートと共通していますが、両者には重要な違いがあります。

バブルソートでは、毎回のパスにおいて隣接する要素同士を比較して並べ替えます。一方、コムソートでは、あらかじめ決めた一定のギャップ（間隔）を空けた要素同士を比較します。そして、各パスが完了するたびにギャップを縮小していき、最終的にギャップが1になった時点でバブルソートと同じ動作になります。

ギャップを縮小する際の係数（シュリンクファクター）は 1.3 が推奨されています。つまり、各パスが終わるごとにギャップの値を1.3で割っていくことになります。この手法により、バブルソートの弱点である「亀」（配列の末尾近くにある小さな値）の移動が遅い問題を効率的に解消できます。

コムソートの計算量

• 時間計算量： 最良ケースで O(n log n)、平均ケースで O(n²/2^p)（pは増分の数）、最悪ケースで O(n²)
• 空間計算量： O(1)

入力と出力

入力：
ソートされていないデータ列：108 96 23 74 12 56 85 42 13 47

出力：
ソート前の配列：108 96 23 74 12 56 85 42 13 47
ソート後の配列：12 13 23 42 47 56 74 85 96 108

アルゴリズム

CombSort(array, size)

入力： データの配列と、配列内の要素の総数

出力： ソート済みの配列

Begin
    gap := size
    flag := true
    while gap ≠ 1 OR flag = true do
        gap = floor(gap/1.3) // 除算後の切り捨て値
        if gap < 1 then
            gap := 1
        flag = false

        for i := 0 to size – gap - 1 do
            if array[i] > array[i+gap] then
                swap array[i] with array[i+gap]
                flag = true;
        done
    done
End

C++による実装例

#include<iostream>
#include<algorithm>
using namespace std;

void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}

void combSort(int *array, int size) {
    int gap = size; // ギャップの初期値を配列サイズに設定
    bool flag = true;

    while(gap != 1 || flag == true) {
        gap = (gap*10)/13; // シュリンクファクターでギャップを縮小
        if(gap<1)
            gap = 1;
        flag = false;

        for(int i = 0; i<size-gap; i++) { // ギャップを空けて要素を比較
            if(array[i] > array[i+gap]) {
                swap(array[i], array[i+gap]);
                flag = true;
            }
        }
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n]; // 指定された要素数で配列を作成
    cout << "Enter elements:" << endl;

    for(int i = 0; i<n; i++) {
        cin >> arr[i];
    }

    cout << "Array before Sorting: ";
    display(arr, n);
    combSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter elements:
108 96 23 74 12 56 85 42 13 47
Array before Sorting: 108 96 23 74 12 56 85 42 13 47
Array after Sorting: 12 13 23 42 47 56 74 85 96 108