Shellsort研究、最適ギャップは未解決
「挿入ソートは遅い、でもクイックソートは重い…」そんな場面でよく勧められるのがシェルソート。
とはいえ“ギャップ数列は何を選ぶ？計算量は？”で手が止まりがち。
この記事は、図解・実装・数列の選び方までを一本道で整理。学習用にも実務の小配列チューニングにも効く、持ち帰れる知識にしました。ウィキペディア
1. シェルソートとは
1-1. 基本の考え方
1-1-1. h-ソート（間隔ソート）の直感
シェルソートのコア発想は、「離れた要素同士の挿入ソートを段階的に行い、最後に h=1 の挿入ソートで仕上げる」というものです。
配列を h ごとに区切って“飛び飛びの列（h 間隔の部分列）”を作り、それぞれを挿入ソートで整序します。
すると、遠距離にある要素を大きく移動できるため、序盤で乱雑さ（逆転）が一気に減り、最終パス（h=1）は“ほぼ整った配列”に対する軽い仕上げになります。
性能をほぼ決めるのがギャップ（h 値）の設計です。ギャップの並べ方・刻み・比率が悪いと、無駄なパスや比較が増え、せっかくの段階整序が目減りします。
逆に、緩やかに縮む良い列を使えば、比較回数・移動回数を抑えつつ最終パスの負荷を最小化できます。
実装面では、“最後のギャップは必ず 1”であることが正しさの前提（最終パスが通常の挿入ソートになる）で、ソートの安定性は“ない（不安定）”ことにも注意が要ります。
ユースケースは、小〜中規模配列の仕上げ、再帰や追加メモリを避けたい環境、あるいは他の高速ソート（クイック等）のサブ手順など。
なお、現代的な観点でも「ギャップ次第で計算量の理論評価や実測が大きく揺れる」ことは広く認識されており、アルゴリズム自体の理解と同じくらいギャップ設計が重要です。(ウィキペディア)
2. 動作イメージと手順
2-1. 例で理解する
2-1-1. ステップ図解で追う
具体例で流れを固めます。たとえばギャップ列を 5→3→1 とする場合、最初に配列を 5 間隔の 5 本の列に分け、それぞれを挿入ソートします（例：インデックス 0,5,10…／1,6,11… などの部分列）。
次にギャップを 3 に縮めると 3 本の列に再編され、再び各列を挿入ソート。最後に h=1 で全体を通常の挿入ソートとして整序すれば完了です。
ここで大事なのは、**「粗い並び替え→中くらい→細かい仕上げ」という三段のリズムです。最初の粗いパスで大きなズレを一掃し、後段のパスで微細なズレを削っていくため、最終パスのコストが劇的に下がるのが直感的にも分かります。
各パスは“そのギャップごとの挿入ソート”であり、アルゴリズムは単純です。
実装では、ギャップ列を大きい順に取り出してループし、各ギャップごとに i=gap..n-1 で走査して“ギャップ幅の挿入法”を適用します。
ステップ実例は教科書的にもよく示され、「最後のギャップは 1」**という要件が例示とともに強調されます。
この流れを頭にいれておくと、後段のギャップ設計の話（なぜ 2.25 倍前後が効くのか、など）も腹落ちしやすくなります。(ウィキペディア)
3. ギャップ（間隔）数列の選び方
3-1. 古典と理論
3-1-1. Shell／Knuth／Hibbard／Pratt
Shell の原案は「⌊N/2⌋, ⌊N/4⌋, …, 1」のように配列長に依存して半分ずつ縮めるシンプルな列ですが、最悪計算量は Θ(N²) に及びます。
Hibbard（2^k−1）や Papernov–Stasevich など奇数中心・幾何学的に増える列は、古典的理論でO(N^{3/2}) 程度の上界が知られ、実測でも原案より良いことが多いです。
**Knuth（(3^k−1)/2）**は実装しやすく、実務でもよく使われる定番。理論面では **Pratt（3-smooth 数：2^p3^q）の列を使うと、既知の中で最良の最悪計算量 O(N log²N) を達成します（ただし刻みが細かすぎてパス数が増えがちで、実用上は重くなりやすい）。
総じて、「1 を必ず含む降順列」であることは正しさの条件で、平均性能は“列の形状（比率の滑らかさ・互いの公約数の小ささ・奇偶構成）”**に強く依存します。
理論最適や平均計算量は今なお研究継続中で、実務では性能と実装容易性の折り合いで列を選ぶのが現実解です。(ウィキペディア, SCE Web, MIT数学)
4. 実務で使われる数列
4-1. 実践派の定番
4-1-1. Tokuda・Ciura・最新γの比較
現場で人気が高いのは Tokuda 列と Ciura 列です。Ciura（1,4,10,23,57,132,301,701…）は乱択配列に対する平均比較回数が良好という経験的評価が広く共有され、701 以降は概ね ×2.25 倍で拡張するのが実用上の定番です。
Tokuda は再帰式 h’₁=1, h’ₖ=2.25·h’ₖ₋₁+1, hₖ=⌈h’ₖ⌉ で生成でき、**“実装が簡単で実務向けに推奨”**とされます。
さらに近年は、Tokuda を連続化した **γ-sequence（Lee, 2021）のように、実験的に Tokuda を上回る比較回数を示す報告もあります（配列サイズや評価関数に依存）。
結論として、「まず Ciura or Tokuda を採用し、プロファイルで γ などを当ててみる」**のが無難な導入手順です。
要件（最大 N、安定性不要、コード長、可搬性など）によって使い分けましょう。
特に組み込みや小配列では、短い列でオーバーヘッドを抑えやすい Ciura/Tokudaが堅実です。(ウィキペディア)
参考（一次情報・最新動向）
・Ciura（2001）平均ケース最良クラスの実験的結果。
・Lee（2021）Tokuda 改良の γ-sequence 提案（平均比較回数改善の報告）。(シュプリンガーリンク, arXiv)
5. 計算量の現在地
5-1. どこまで速いのか
5-1-1. 最悪・平均・未解決の整理
計算量はギャップに依存します。古典列（Shell など）では最悪 Θ(N²) が避けられません。
一方で Pratt の 3-smooth 列は理論上最悪 O(N log²N) を達成し、現時点の既知の最良上界です。
ただしパス数が増え実用上は遅くなりがち。Hibbard など多くの幾何列では O(N^{3/2}) 程度の上界が示され、古典研究でも支持されています。
平均計算量（乱択配列での比較回数の期待値）は列ごとに挙動が変わり、最適列の存在・一般形の平均オーダーは今もオープンな側面があります。
実務的には、「連続比が約 2.2〜2.3」で滑らかに縮む列（Tokuda／Ciura 拡張など）が比較回数・移動回数のバランスが良好という経験則が多くの実験で観察されています。
重要なのは、オーダーの理論最良＝常に実測最速ではない点です。
メモリ階層・分岐予測・キャッシュ局所性・言語実装のコストを踏まえ、プロファイルで“自分のデータ”に最適化するのが最短路になります。(SCE Web, MIT数学)
6. 実装とチューニング
6-1. Pythonで押さえる
6-1-1. 実務向けの実装・注意点
実装はギャップ列のループ内で“ギャップ幅の挿入ソート”を適用するだけです。
典型例は Ciura：[701,301,132,57,23,10,4,1] を降順に回し、各 gap に対して for i in range(gap, n) とし、temp=a[i] を保持→ j を gap ずつ戻しながら a[j-gap] > temp の間シフト→最後に a[j]=temp。
注意点は、(1) gap=1 を必ず含める（整列の保証）、
(2) 安定ではないため等値の相対順序は保持されない、
(3) ギャップは降順（小→大にすると前段の効果が相殺されやすい）、
(4) テストは4種（乱択・逆順・等値多め・ほぼ整列）で最低限回す、
(5) プロファイル前提でギャップ列を差し替え可能に作る、の5点。
さらに実務では、ある閾値以下の小配列はシェルソートで仕上げ、それ以上は別ソート（クイック/ヒープ/ティムソート等）というハイブリッドが定番。
qsort の組み込み実装（uClibc など）で採用例があるのは、“コードが短い、スタックを使わない、追加メモリ O(1)”という特性が理由です。
まずは Ciura か Tokuda を実装してベースラインを作り、対象データで γ-sequence 等を AB テストする流れを推奨します。(ウィキペディア, programiz.com)
7. 使いどころとFAQ
7-1. いつ選ぶ？
7-1-1. 安定性／小配列／ハイブリッド活用
Q1：安定ですか？―不安定です。等値の相対順序が重要なら安定ソート（マージ/TimSort など）を選びましょう。
Q2：どんな場面で強い？―小配列の仕上げ、再帰や例外コストを避けたい組み込み、割り込みが入りやすい環境、qsort の実装差し替えなどで使われます。大規模・厳密な最悪保証が必要なら別手段が無難。
Q3：ギャップは多いほど速い？―やみくもに増やすとパスのオーバーヘッドが支配して逆効果。“緩やかに縮む比率（≈2.2〜2.3）”と互いに小さな公約数を持つ列が経験的に好成績です。
Q4：どの列が最適？―未解決領域です。Ciura／Tokuda／Pratt／γ など候補をプロファイルで比較するのが実務的最適化。
Q5：他ソートとの関係は？―ハイブリッドが王道。大枠で高速なアルゴリズムを使い、閾値以下でシェルソートに切替えると、分岐予測・キャッシュ・関数呼び出しのコストを抑えられます。
キモは「自分のデータで測る」。教科書的な最悪オーダーや一般論だけでは最速構成は決まりません。(ウィキペディア)
＼ 最新情報をチェック ／
