シェルソートとは？仕組み・計算量・C++実装コードをわかりやすく解説

シェルソート（Shell Sort）は、挿入ソートを改良したソートアルゴリズムです。通常の挿入ソートでは、要素を正しい位置に挿入する際に、隣接要素との比較・移動を繰り返すため、大きなブロックを何度もシフトしなければならないケースがあります。

シェルソートでは、あらかじめ一定の間隔（ギャップ）を設定して離れた位置にある要素同士を比較・交換することで、大規模なデータ移動を効率的に削減できます。各パスが終了するごとにギャップを半分に縮小していき、最終的にギャップが1になった時点でほぼ整列された状態になるため、挿入ソートよりも高速に動作します。

シェルソートの計算量

• 時間計算量： 最良の場合は O(n log n)。その他のケースでは、採用するギャップ列（間隔の減らし方）に依存します。
• 空間計算量： O(1) — 入力配列以外に追加のメモリをほとんど必要としません。

入力と出力の例

入力:
未ソートのリスト: 23 56 97 21 35 689 854 12 47 66

出力:
ソート前の配列: 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 ずつ減少させながら繰り返す
                もし array[k+gap] >= array[k] ならば
                    break
                そうでなければ
                    array[k + gap] と array[k] を入れ替える
            done
        done
    done
End

C++による実装例

#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) {      //初期ギャップは 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 << "要素数を入力してください: ";
    cin >> n;
    int arr[n]; //指定された要素数で配列を作成
    cout << "要素を入力してください:" << endl;

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

    cout << "ソート前の配列: ";
    display(arr, n);
    shellSort(arr, n);
    cout << "ソート後の配列: ";
    display(arr, n);
}

実行結果

要素数を入力してください: 10
要素を入力してください:
23 56 97 21 35 689 854 12 47 66
ソート前の配列: 23 56 97 21 35 689 854 12 47 66
ソート後の配列: 12 21 23 35 47 56 66 97 689 854