シェルソートとは
シェルソートとは、
です。
シェルソートは、挿入ソートの欠点を改善し、より効率的にデータを整列させるソートアルゴリズムです。
挿入ソートについてはこちらの記事で解説しています。
アルゴリズムの概要
データを分割して小さくし、それぞれに対して挿入ソートを繰り返していきます。
(挿入ソートはほぼソートされたデータに対して高速で処理できるという特性を利用しています。)
挿入ソートのアルゴリズム
-
-
ステップ1データを一定間隔(ギャップ)ごとにグループ分けする
-
ステップ2各グループ内で挿入ソートを行う
-
ステップ3ギャップを徐々に小さくしていき、ステップ1,2を繰り返すギャップが最終的に1になるまで繰り返す
-
今回はギャップを4→3→1と小さくしていく例を示します。
gap=4で挿入ソート
gap=3で挿入ソート
gap=1で挿入ソート
性能
時間計算量
時間計算量は以下の通りです。
ギャップの例
- シェルの原案：N/2, N/4, …, 1
- Knuthの列：1, 4, 13, 40, …, (3^k – 1) / 2
- Sedgewickの列：1, 8, 23, 77, 281, 1073, 4193, 16577, …
空間計算量
空間計算量は、 \(O(1)\)（インプレース実装可能）
特徴
長所
短所
用途
実装(Python)
def selection_sort(nums, start, gap):
for unsorted_head in range(start + gap, len(nums), gap):
for i in range(unsorted_head, start, -gap):
if nums[i - gap] <= nums[i]:
break
nums[i], nums[i - gap] = nums[i - gap], nums[i]
def shell_sort(nums):
gap = len(nums) // 2
while gap > 0:
for start in range(gap):
selection_sort(nums, start, gap)
gap //= 2
nums = [8, 6, 3, 5, 9, 2, 1, 4, 7]
shell_sort(nums)
print(nums)[1, 2, 3, 4, 5, 6, 7, 8, 9]
参考文献
コメント