シェルソートとは?挿入ソートを進化させた効率的ソートアルゴリズムを図解で解説

スポンサーリンク
シェルソートとは?挿入ソートを進化させた効率的ソートアルゴリズムを図解で解説 アルゴリズム

シェルソートとは

シェルソートとは、

数列を昇順に並び替えるアルゴリズムの1つ

です。

 

シェルソートは、挿入ソートの欠点を改善し、より効率的にデータを整列させるソートアルゴリズムです。

挿入ソートについてはこちらの記事で解説しています。

 

アルゴリズムの概要

データを分割して小さくし、それぞれに対して挿入ソートを繰り返していきます。

(挿入ソートはほぼソートされたデータに対して高速で処理できるという特性を利用しています。)

挿入ソートのアルゴリズム
    • ステップ1
      データを一定間隔(ギャップ)ごとにグループ分けする
    • ステップ2
      各グループ内で挿入ソートを行う
    • ステップ3
      ギャップを徐々に小さくしていき、ステップ1,2を繰り返す
      ギャップが最終的に1になるまで繰り返す

今回はギャップを4→3→1と小さくしていく例を示します。

gap=4で挿入ソート

gap4で挿入ソート_1

gap4で挿入ソート_2

 

gap=3で挿入ソート

gap3で挿入ソート

 

gap=1で挿入ソート

gap1で挿入ソート_1

gap1で挿入ソート_2

 

性能

時間計算量

時間計算量は以下の通りです。

時間計算量
  • 平均時間計算量: ギャップ列に依存(一般的に\(O(N^{1.3})からO(N^{1.5})\)と言われている)
  • 最良の場合(ほぼソート済み): \(O(Nlogn)\)
  • 最悪の場合(逆順): \(O(N^2)\)

ギャップの例

  • シェルの原案: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]

 

参考文献

Sorting Algorithms Animations | Toptal®

コメント

タイトルとURLをコピーしました