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

コムソートとは

コムソート（Comb Sort）は、バブルソートを改良したソートアルゴリズムです。基本的な考え方はバブルソートと共通していますが、両者には重要な違いがあります。バブルソートでは常に隣接する要素同士を比較するのに対し、コムソートではあらかじめ設定された「ギャップ（間隔）」を使って、離れた位置にある要素同士を比較します。

各パス（走査）が完了するたびにギャップは縮小されていきます。このとき用いられる縮小係数（シュリンクファクター）は1.3で、つまり各パスの終了後、ギャップの値を1.3で割っていくことになります。

計算量（時間計算量）

• 最良ケース：O(n log n)
• 平均ケース：O(n²/2^P)（Pは増分の数）
• 最悪ケース：O(n²)

アルゴリズム

CombSort(array, size)

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

出力 − ソート済みの配列

Begin
    gap := size
    flag := true
    while the 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);
}

コードのポイント

この実装では、まずギャップの初期値を配列のサイズに設定します。ループの各回で gap = (gap*10)/13 と計算することで、1.3で割る操作を整数演算で実現しています。ギャップが1未満になった場合は1に固定されます。

変数 flag は、そのパスで要素の交換が一度でも発生したかどうかを追跡するためのものです。ギャップが1になり、かつ交換が一切行われなくなった時点でソートが完了したと判断され、ループが終了します。

実行結果

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