概要
今日はシェルソートについて学んだ。
学んだこと
- 挿入ソートの改良版
- 挿入ソートの最良計算量：O(n)
シェルソートは、挿入ソート（Insertion Sort）を改良したソートアルゴリズム。 1959年にドナルド・シェル（Donald Shell）によって考案された。
挿入ソートは、近くの要素を比較して入れ替える仕組みのため、 すでにほとんど整っているデータにはとても速く動く。 でも、バラバラなデータが多いと時間がかかる。
そこで、シェルソートでは「離れた位置にある要素同士を先に並び替えてしまおう！」という工夫を加える。
シェルソートは「引っ越しの荷造り」に似ている。 最初に部屋ごとにざっくりと不要なものを捨てて、 次に箱ごとに整理し、最後に段ボールの中を丁寧に整えるような流れ。 最初に大雑把な整理をすることで、後の細かい作業がスムーズになる点が共通している。 いきなり小さなものを一つずつ整理するより、段階的に効率よく進められるのが特徴。
シェルソートのアルゴリズム
- 間隔hで挿入ソート
- hを狭めながら繰り返す
- 間隔hに依存、完全に最適な間隔hは未解決
参考文献
https://medium-company.com/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88/