シェルソート — ギャップシーケンスとその影響

シェルソートの動作原理

シェルソートは、離れた位置のアイテム交換を可能にする挿入ソートの一般化です。特定のギャップ離れた要素のソートから始め、ギャップが1になるまで（その時点で標準的な挿入ソートがほぼソート済みの配列に対して実行される）徐々にギャップを縮小します。

アルゴリズム

function shellSort(arr):
  n = length(arr)
  gap = floor(n / 2)
  while gap > 0:
    for i = gap to n-1:
      temp = arr[i]
      j = i
      while j >= gap and arr[j - gap] > temp:
        arr[j] = arr[j - gap]
        j -= gap
      arr[j] = temp
    gap = floor(gap / 2)

ギャップが重要な理由

重要な洞察は、最後のギャップ1のパスが実行されるとき、以前のより大きなギャップのパスにより配列がすでにほぼソートされていることです。挿入ソートはO(n + d)（dは転倒数）で実行され、以前のパスが転倒数を大幅に削減するため、総作業量はO(n²)よりはるかに少なくなります。

ギャップシーケンスの比較

シーケンス	値	最悪ケース計算量
Shell（1959）	n/2, n/4, ..., 1	O(n²)
Hibbard（1963）	2ᵏ - 1: 1, 3, 7, 15, ...	O(n^(3/2))
Sedgewick（1986）	1, 5, 19, 41, 109, ...	O(n^(4/3))
Ciura（2001）	1, 4, 10, 23, 57, 132, 301, 701	経験的に最良
Tokuda（1992）	Ceil((9ᵏ - 4ᵏ)/(5*4ᵏ⁻¹))	O(n^(4/3))推測

Ciuraギャップシーケンス

Ciuraのシーケンス [1, 4, 10, 23, 57, 132, 301, 701] は広範な経験的テストにより発見され、実用的な配列サイズで最少の比較回数を生成します。

特性

• 不安定: ギャップパス中に等しい要素を越えて移動する可能性がある
• インプレース: O(1)追加空間
• 適応的: 部分的にソートされた入力の恩恵を受ける
• 証明された最適ギャップシーケンスなし: 最良のギャップシーケンスは計算機科学の未解決問題