シェルソート徹底ガイド：仕組み・ギャップ列の選び方・実装最適化と計算量の解説
エバープレイ編集部シェルソートとは
シェルソート（Shell sort）は、1959年にドナルド・シェル（Donald L. Shell）が発表したソートアルゴリズムで、単純挿入ソートを「ギャップ（間隔）」を用いて拡張したものです。基本的な考え方は、まず離れた要素同士を比較・整列することで配列全体の乱れを粗く減らし、最後にギャップを1（通常の挿入ソート）にして細かく整列するというものです。インプレースで動作し、追加の大きなメモリを必要としない点と実装の簡潔さから、古くから実務や教育でよく扱われてきました。
アルゴリズムの仕組み
シェルソートの流れは次のようになります。
- 配列長 N に対して、まずある一連のギャップ（間隔）列を決める（例：N/2, N/4, ..., 1 など）。
- 各ギャップ g に対して、配列を g 間隔ごとの部分列（すなわち「g-ソート」）に分け、それぞれに対して挿入ソート相当の処理を行う。つまり、位置 i と i+g の要素を比較・挿入して g 間隔の整列を行う。
- ギャップを徐々に小さくして最終的に g = 1 になったとき、配列はほぼ整列されているため、1-ソート（通常の挿入ソート）で高速に完了する。
重要なのはギャップ列の選び方で、これによってアルゴリズムの実行時間（特に最悪ケース）が大きく変わります。
簡単な擬似的手順（説明）
擬似コード風に説明すると：
- ギャップ列 gap[] を用意する（降順に並べる）。
- for each g in gap[]:
- for i = g to N-1:
- temp = A[i]; j = i;
- while j >= g and A[j-g] > temp:
- A[j] = A[j-g]; j -= g;
- A[j] = temp;
- for i = g to N-1:
上の while 部分が「g 間隔の挿入ソート」に相当します。要素をスワップするより、ずらして最後に挿入する手法（シフト法）が一般に効率的です。
ギャップ列（間隔）の種類と影響
シェルソートの性能はほとんどギャップ列に依存します。代表的なものを挙げます。
- Shell（元の提案）: N/2, N/4, ..., 1 — 実装は簡単だが最悪計算量は O(N²)。
- Hibbard（2^k − 1）: 1, 3, 7, 15, ... — 理論解析で改善が見られ、最悪計算量は O(N^(3/2)) とされるケースがある。
- Knuth: (3^k − 1)/2 系列 — 実装で人気があり、経験的に良好。
- Sedgewick: いくつかの改良系列を提案（例: 1, 5, 19, 41, 109, ... 等）。理論的に良い最悪ケース境界が示される系列もある。
- Pratt（2^i 3^j の全組合せ）: 全ての 2^i·3^j を含む系列で、理論上の最悪ケースは O(N log² N) と分析される。
- Ciura（経験則）: 最初に報告された系列は 1, 4, 10, 23, 57, 132, 301, 701, 1750 ...。実務上の配列長に対して非常に良好な経験的性能を示し、多くの実装で採用・拡張されている。
まとめると、ギャップ列を賢く選べば最悪ケースのオーダーは二乗から大幅に改善でき、実務レベルでは Ciura などの経験的系列がよく用いられます。
計算量とアルゴリズム的性質
- 最悪計算量: ギャップ列に依存。Shell の元の列は O(N²)。Pratt 系列では O(N log² N)、Sedgewick 系列ではより良い理論的上界（例: O(N^(4/3)) に関連する解析）など報告がある。
- 平均計算量: ギャップ列と入力分布に依存するため一概には言えないが、良い系列では経験的に O(N^1.25)〜O(N^1.5) 程度の挙動を示すことが多い。
- 空間計算量: インプレース（追加の大きな配列を必要としない）、O(1) 追加メモリ。
- 安定性: デフォルトの実装では安定ではない（等しいキー間の相対順序は維持されない）。安定にするには追加検討が必要。
- 適応性: 部分的に適応的。配列が既にほぼ整列されている場合、高速に動作する傾向がある。
実装上の注意・最適化
- 移動方法: 逐次スワップよりも「シフトして最後に挿入する」方式（挿入ソートと同様）が一般にデータ移動を減らせる。
- ギャップ列の準備: 実務では Ciura 系列を先に試し、配列長を超えたら適宜拡張して使う方法が好まれる。
- データ型: 比較コストや移動コストによって最適化方針が変わる（重いオブジェクトならポインタ/参照を動かす、軽量な整数なら直接移動を行う等）。
- 小配列処理: 最終的に g = 1 の挿入ソートが行われるため、小さな配列ではシェルソート単体で十分に高速。
比較：どんな場面で使うべきか
長所と短所を整理します。
- 長所:
- 実装が比較的簡単で、追加メモリがほとんど不要。
- 小～中規模の配列では非常に高速（良いギャップを選べば）。
- 挿入ソートに比べて遠く離れた要素の不整合を早期に解消できる。
- 短所:
- 最適なギャップ列は理論的・経験的な研究に依存し、万能の列はない。
- 大規模なランダムデータでは、チューンされたクイックソート／ヒープソート／マージソート等より遅くなることが多い。
- 安定ではないので、安定ソートが必要なら工夫が必要。
結果として、標準ライブラリの主要なソート関数（C++のstd::sort、PythonのTimsort など）は一般にシェルソートを使わず、より安定で/あるいは大規模データに強いアルゴリズムが採用されています。ただし組み込み用途やメモリ制約が厳しい場面、小・中規模データの高速ソートにはシェルソートが適していることがあります。
簡単な実行例（概念の確認）
配列 [8, 5, 3, 7, 1, 9, 2] に対してギャップ列 [3, 1] を使うと：
- g = 3 のとき、3-ソートを実行 → 部分列ごとに挿入操作を行い、遠い不整合を減らす。
- g = 1 のとき、通常の挿入ソートで最終整列 → この段階ではほとんど整列済みなので少ない移動で済む。
このように段階的に乱れを減らしていくのがシェルソートの直感的な利点です。
まとめ
シェルソートは「減少するギャップで挿入ソートを繰り返す」ことで高速化を図る古典的アルゴリズムです。ギャップ列の選び方が性能の鍵であり、理論的な評価と経験的なチューニングの両面で多くの研究がなされてきました。実装は簡単でメモリ効率が高く、小〜中規模データでは有力な選択肢になり得ますが、非常に大きなデータや安定性が求められる場面では他のアルゴリズムが好まれることが多い点に注意してください。
