シェルソートを実装するC++プログラム

シェルソート（Shell Sort）は、挿入ソートを改良した整列アルゴリズムです。通常の挿入ソートでは、要素を正しい位置に挿入するために大量のデータをまとめてシフト（移動）する必要がある場合があります。シェルソートでは、あらかじめ一定の間隔（ギャップ）ごとに離れた要素同士を比較・交換することで、大規模なシフト処理を大幅に減らすことができます。

整列は特定の間隔で行われ、各パスが終了するたびにギャップを半分に縮小していき、最終的にギャップが1になれば完全に整列された状態になります。

シェルソートの計算量

• 時間計算量：最良ケースは O(n log n)。その他のケースでは、採用するギャップ列（間隔の選び方）に依存します。

• 空間計算量：O(1)（追加のメモリはほとんど不要）

入力 − 未整列のリスト：23 56 97 21 35 689 854 12 47 66
出力 − 整列後の配列：12 21 23 35 47 56 66 97 689 854

アルゴリズム

shellSort(array, size)

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

出力：整列済みの配列

Begin
    gap := size / 2 から開始し、gap > 0 の間、gap を gap / 2 ずつ更新しながら繰り返す
        j := gap から size - 1 まで繰り返す
            k := j - gap から 0 まで、gap ずつ減らしながら繰り返す
                if array[k+gap] >= array[k] ならば
                    break（ループを抜ける）
                else
                    array[k + gap] と array[k] を交換する
            done
        done
    done
End

サンプルコード

#include<iostream>
using namespace std;
void swapping(int &a, int &b) {     // a と b の中身を交換する
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void display(int *array, int size) {
    for(int i = 0; i<size; i++)
        cout << array[i] << " ";
    cout << endl;
}
void shellSort(int *arr, int n) {
    int gap, j, k;
    for(gap = n/2; gap > 0; gap = gap / 2) {     // 初期値 gap = n/2、
        // 以降は gap / 2 ずつ減少させる
        for(j = gap; j<n; j++) {
            for(k = j-gap; k>=0; k -= gap) {
                if(arr[k+gap] >= arr[k])
                    break;
                else
                    swapping(arr[k+gap], arr[k]);
            }
        }
    }
}
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);
    shellSort(arr, n);
    cout << "Array after Sorting: ";
    display(arr, n);
}

実行結果

Enter the number of elements: 10
Enter elements:
23 56 97 21 35 689 854 12 47 66
Array before Sorting: 23 56 97 21 35 689 854 12 47 66
Array after Sorting: 12 21 23 35 47 56 66 97 689 854

このように、シェルソートはギャップを段階的に狭めながら整列を進めることで、挿入ソート特有の大規模なデータ移動を回避できます。特に中規模程度のデータに対して効率的に動作するため、実用的な整列手法の一つとして広く知られています。