1. tomabou

    No comment

    tomabou
Changes in body
Source | HTML | Preview
@@ -1,78 +1,78 @@
## はじめに
ソートは最もよく使われるアルゴリズムのうちの一つで、ソートするアルゴリズムは様々なものが知られています。
クイックソートやマージソートは有名でしょう。それらのアルゴリズムに比べると少し知名度が低いかもしれませんがシェルソートというソートアルゴリズムも存在しています
シェルソートの計算量は気持ち悪いのですが、そんなところも可愛らしく思えてきたので紹介します
## 挿入ソート
シェルソートは挿入ソートを改良したアルゴリズムです。
挿入ソートは基本的なアルゴリズムで計算量が$O(n^2)$ です。クイックソートやマージソートは平均計算量が$O(nlogn)$であることを考えると非常に低速です。ただ、だいたいソートされていれば計算量は$O(n)$に近い値となります。正確にいえばソートされた状態から反転しているペア`i<j and a[i] > a[j]`の個数が必要な計算量です。バブルソートなどと同じですね。
## シェルソート
シェルソートは挿入ソートを部分列に対して何回か行うアルゴリズムです。
1. 間隔hをえらび、間隔がhである部分列h個に数列を分割する。例えばhが3ならば、$(a_0,a_3,...),(a_1,a_4,...),(a_2,a_5,...)$となる。
1. それぞれに対して挿入ソートを行う
2. hが1ならソートされている
2. hを小さくして1に戻る
挿入ソートは要素が大きく動くのが苦手なのですが、要素が大きく動けるようにすることで高速になることを期待するアルゴリズムです。
そこそこ高速なソートアルゴリズムの中ではアルゴリズムを実行するために必要なメモリ数が非常に少なく、メモリがシビアな組み込み系などでは使われているという噂を聞いたことがあります。
## 計算量
-以上で述べたシェルソートは一体どれほどなのでしょうか。実はこれは非常に難しい問題です。シェルソートの計算量は間隔をどのように取るかに依存しています。最悪計算量が解析されている間隔列は数多くあり、有名なものは英語版Wikipedia https://en.wikipedia.org/wiki/Shellsort にまとめられています。平均計算量が解析されているものはほとんどなくほとんが未解決問題です。また平均計算量が$O(n\log n)$となるような間隔列が存在するかどうかも未解決問題です
+以上で述べたシェルソートの計算量は一体どれほどなのでしょうか。実はこれは非常に難しい問題です。シェルソートの計算量は間隔をどのように取るかに依存しています。最悪計算量が解析されている間隔列は数多くあり、有名なものは英語版Wikipedia https://en.wikipedia.org/wiki/Shellsort にまとめられています。平均計算量が解析されているものはほとんどなくほとんが未解決問題です。また平均計算量が$O(n\log n)$となるような間隔列が存在するかどうかも未解決問題です
いくつか上げてみると
$ \frac{N}{2} , \frac{N}{4}, \frac{N}{8},..$
これは最悪計算量$O(n^2)$, 平均計算量は$O(n^{1.5})$,でshellが最初に提案した論文で用いられていたものです。
$ \frac{3^k-1}{2}$
最悪計算量$O(n^{1.5})$,これはknuthの本で紹介されているもので平均計算量は未解決ですが$O(n^{1.25})$と予想されています
素因数が2,3しかないような数全体
最悪計算量$O(n\log^2n)$, 現状最悪計算量がもっとも良い間隔列のうち一つです。
## 最悪計算量の評価の証明
最悪計算量が$O(n\log^2n)$ である証明はきれいなので紹介します。
p-orderd というのを `a[i] < a[i+p] `が常に成り立っているものとすることにします。
シェルソートの間隔hのステップのあとはh-orderdになっています。
シェルソートの一回のステップのことをh-sortと呼ぶことにします。
間隔hで取った部分列のことをh-chainと呼ぶことにします
#### x-orderd な数列をy-sortしてもx-orderd
a[i]<a[i+x]であったとする。xがyの倍数ならば自明。そうでないとする。
y-sortすると、a[i]はa[i+ny]として書ける要素(y-chainとなる)と交換される可能性があり、
a[i+x]はa[i+x+ny]として書ける要素と交換される可能性がある。
a[i]が属するy-chainをA, a[i+x]が属するy-chainをBとする。
a[i+x]がBの中でt番目に小さいとする。すると、Bの中にa[i+x]以下の要素がt個存在し、それに対応するAの要素を考えると、Aの中にa[i+x]より小さい要素がt個存在する。
よってAの中でt番目に小さい要素はa[i+x]よりも小さい。
よってAとBをどちらもソートしても、x-orderdという性質は保たれる。
#### 2-orderdで3-orderdな数列を挿入ソートするとO(n)
任意の2より大きな数は$2n+3m$と書けるため、任意の2以上の数pに対してp-orderdになっている。
よって、任意の要素について、反転している要素として考えられるのは隣り合った2つの要素のみ。
よって反転しているペアの数は$O(n)$である。
よって挿入ソートの計算量は$O(n)$
このことより、2p-orderdかつ3p-orderdな数列をp-sortするときの計算量は$O(n)$である。
素因数が2と3のみのN以下の数は$O(\log^2n)$個である。
素因数が2と3のみの数を間隔列としてシェルソートを行うと、p-sortするときはもうすでに2p-sortと3p-sortされた後であり、2p-orderdかつ3p-orderdされた数列となっている。
よって一回のステップが$O(n)$でおわり全体で$O(n\log^2n)$である。
以上より示された
## 終わりに
ソートアルゴリズムは基本的な話かと思いきや、ソートアルゴリズムは最近でもトップカンファレンスに時折論文が投稿されるホットで未開拓の分野です。
みなさんもぜひシェルソートの平均計算量を解析してみてください。