Programming Magic

シェルソートは挿入ソートを改良したソートアルゴリズムで、データを間隔hごとのグループに分けてそれぞれ挿入ソートを行うという操作を、hを徐々に減らしながら繰り返しデータ全体をソートする。

単純に考えるとシェルソートは挿入ソートを繰り返し実行しているので挿入ソートよりも遅くなりそうだが、交換回数が少なくなるので高速にソートすることができる。 シェルソートでは間隔hの決め方が重要で、実際に実験してみたところ間隔hを変えるだけで実行速度に10倍以上の差が出た。

シェルソートでの間隔hを決めるときにはh₀ = 1としてh_n+1 = 3*h_n+1やh_n+1 = 2*h_n+1のようなh_n+1 = a*h_n+bという形の漸化式を使うことが多い。例えば、1000個のデータに対してh_n+1 = 3*h_n+1を使うと間隔hは364, 121, 40, 13, 4, 1と減っていく。

この漸化式h_n+1 = a*h_n+bのaとbの値を変えるだけでも実行速度が大きく変わることがある。ランダムに生成した100万個のデータに対してa = 2 ～ 20、b = 0 ～ 20の範囲でそれぞれ100回ずつシェルソートを実行する実験を行ったところ、最も遅いものがa = 20、b = 0で平均6.012秒、最も早いものがa = 3、b = 1で平均0.392秒と約15倍もの差が出た。

この実験結果をヒートマップで表示すると以下のようになる。横軸がaの値で、縦軸がbの値、色が実行速度を表している。この結果からb = 0やa = bとなる値は避けた方が良さそうだとわかる。

間隔hを決める式はh_n+1 = a*h_n+bという形の漸化式以外にも様々な式が考えられている。 例えば、h_n = 2ⁿ⁺¹-1やh_n = 9*4ⁿ-9*2ⁿ+1、h_n = 2ⁿ*3ⁿといった式などがあり、複雑なものではfibonacci(i)をフィボナッチ数列のi番目の値としてh_n = floor(fibonacci(n+1)^1+sqrt(5))という式を使うこともある。

h_n+1 = a*h_n+bとは異なる６つの式と挿入ソートでも同様に実験し、先程の結果と合わせて実行速度が速い順に並べると以下のようになった。新しく加えた式の結果は色を変えている。

(※今回実験に使ったソースコードはコレ。)

h_n = 4ⁿ+3*2^n-1+1 (ただし、h₀ = 1)は、最初の結果で最も早かったh_n+1 = 3*h_n+1よりもさらに約1.5倍速いという結果になった。 この差は僅かなのでそれほど気にしなくても良さそうだが、h_n+1 = a*h_n+bの漸化式でb = 0やa = bとなる値を使わないように注意しなければならない。よく見てみるとa = b * 2やa = b / 2、a = b * 3といった場合にも比較的遅くなっているので、この形の漸化式を使うのならとりえあずh_n+1 = 3*h_n+1を使っておくのが無難そうだ。