シェルソートの計算量の紹介

はじめに

ソートは最もよく使われるアルゴリズムのうちの一つで、様々なソートアルゴリズムが知られています。
クイックソートやマージソートは有名です。それらのアルゴリズムに比べると少し知名度が低いですが、シェルソートというアルゴリズムがあります。
シェルソートの計算量は複雑ですが、いくつか紹介したいと思います。

挿入ソート

シェルソートを考える前に挿入ソートについて触れておきます。
挿入ソートは、「ソート済みの部分を順番に見て挿入すべき場所を見つけて挿入する」というシンプルなアルゴリズムで、計算量は$O(n^2)$です 。
クイックソートやマージソートは平均計算量が$O(nlogn)$であることを考えると非常に低速です。しかし、挿入ソートには「だいたいソートされていれば高速にソートできる」という性質があります。
正確に言うと「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,...)$となる。
2. それぞれに対して挿入ソートを行う
3. hが1ならソートされている
4. hを小さくして1に戻る

挿入ソートは要素が大きく動くと多くの要素のcopyが発生して計算量がかかります。要素を大きく動かすことでそのボトルネックが解消され挿入ソートと比べて高速にソートできます（そんな気がする）。
そこそこ高速なソートアルゴリズムの中ではアルゴリズムを実行するために必要なメモリ数が非常に少なく、メモリがシビアな組み込み系などでは使われているという噂です。

計算量

以上で述べたシェルソートの計算量は一体どれほどなのでしょうか。実はこれは非常に難しい問題です。シェルソートの計算量は間隔をどのように取るかに依存しています。最悪計算量が解析されている間隔列は数多くあり、有名なものは英語版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-ordered というのを a[i] < a[i+p] が常に成り立っているものとします。
シェルソートの間隔hのステップのあとはh-orderedです。
シェルソートの一回のステップのことをh-sortと呼ぶことにします。
間隔hで取った部分列のことをh-chainと呼ぶことにします

x-ordered な数列をy-sortしてもx-ordered

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-orderedという性質は保たれる。

2-orderedで3-orderedな数列を挿入ソートするとO(n)

任意の2より大きな数は$2n+3m$と書けるため、任意の2以上の数pに対してp-orderedになっている。
よって、任意の要素について、反転している要素として考えられるのは隣り合った２つの要素のみ。
よって反転しているペアの数は$O(n)$である。
よって挿入ソートの計算量は$O(n)$

このことより、2p-orderedかつ3p-orderedな数列をp-sortするときの計算量は$O(n)$である。

素因数が2と3のみのN以下の数は$O(\log^2n)$個である。
素因数が2と3のみの数を間隔列としてシェルソートを行うと、p-sortするときはもうすでに2p-sortと3p-sortされた後であり、2p-orderedかつ3p-orderedされた数列となっている。
よって一回のステップが$O(n)$でおわり全体で$O(n\log^2n)$である。
以上より示された

終わりに

ソートアルゴリズムは基本的な話かと思いきや、ソートアルゴリズムは最近でもトップカンファレンスに時折論文が投稿されるホットで未開拓の分野です。
みなさんもぜひシェルソートの平均計算量を解析してみてください。