シェルソート単語

シェルソート

シェルソートはソートアルゴリズムの一種。ドナルドシェルが発明したのでシェルソートという。

挿入ソートの発展系で、値がっていない時でもなるべく性が落ちないよう工夫したもの。ただし値がっている時に最速というスプリンター特性と安定ソートの利点は失われてしまった。

実装バリエーションが多いため性はまちまちであり、均計算時間も実はよく分かっていない。典的にはO(n^1.25)

原理

根本的な原理は挿入ソートと同じ。

シェルソートでは挿入ソートの次の二点に注して高速化を図る。

  1. 挿入ソートは値がソート済みに近いほど速いという特性がある
    -> じゃあ大雑把でいいから「大体ソート済み」の配列を先に作れれば速いところだけ使えるよね
  2. 挿入ソートは値を挿入する際の移動距離が長いほど、スライドしなければならない後続列が長くなるという弱点がある
    -> 移動距離に対応するスライド量を減らせれば効率的な長距離移動ができる

具体的には、ソートを一定の間隔でペアにしてそれぞれで挿入ソートを行い、だんだん間隔を狭めていく。例えば、最初は10個おきの組([1,11,21...], [2,12,22...])、次は5個おき([1,6,11...], [2,7,12...])、最後は普通挿入ソート([1,2,3...])といったように段階をおいて並び替える。

こうすると、最後尾の近くから先頭まで値が移動しても、スライドしなければならない量はそれぞれのペアの長さだけで済む。また段階が進めば進むほどソート済み配列に近づいていくので、最後にベタな挿入ソートをしてもそれほど遅くならないというわけである。

考えた人は頭いいね。

性能検討

シェルソートの性はステップの取り方で決まる。実装バリエーションは色々と提案されているがこれが決定版というのはないようだ。英wikipediaexitには色々パターンが載っており、較すると楽しいかもしれない。うまくステップを取ると最悪でもO(n^2)のような酷い数値にはならない。

オーダー的にはまあまあ悪くないものの、性が中途半端なのであまり出番の多くないアルゴリズムである。利点としては、較的実装コンパクトなことと、コールスタックを使わずループだけで素直に処理できる点が組込などに向いていることであろうか。ハマるシチュエーションがないわけではないので、ゴマ程度に覚えておきたい。

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

シェルソート

まだ掲示板に書き込みがありません…以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • シェルソートについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!