TL;DL
柴田望洋先生のご本で Shellsort を勉強していたところ、 アルゴリズムの改良の話題が出ていた。その方法が「間隔」をうまいこと設定して、要素を満遍なく整列していく方法。
間隔が小さすぎるとパスの処理速度が低下し、大きすぎるとオーバーヘッドが生じる。
初期案の D. L. Shell の場合、二分の一に減らしていくのだが、これだとグループ化される要素に偏りがでる。したがって改善案が D. E. Knuth, T. N. Hibbard, R. Sedgewick らにより提出されている。
ここでは前掲の書で紹介されていた D. E. Knuth の方法を考えてみる1。
どんなものなのか
これを読みましょう。
なるほど...で
ここで使う間隔数列の面倒な点は、「大きい方から」使うということ。
Knuth の列は$1, 4, 13, 40, 121, \dots$という数列だが、例えばソートしたいシーケンスの要素数が20であった場合、$13$を選択することになり、41なら$40$を選択することになる。
実際の Shellsort の実装を調べてみると、数列をハードコーディングするか、forでgapを大きくしていき、要素数を超えた時点で打ち切ることによって実装している。
ダサくね？
ということで、考えなければならないのは、要素数以下で最大の間隔 (gap) である2。
数列
Knuth の一般項を求めよう。
一般項を$a_n$とおき、階差数列$b_n=a_{n+1}-a_n$を考えると
- $b_1=3$
- $b_2=9$
- $b_3=27$
となって、初項が$3$、公比も$3$の等比数列が現れる。
従って$b_n=3^n$となるから、$n\ge2$のとき
$$
a_n = 1 + \sum^{n-1}_{k=1} 3^n = \frac{3^n - 1}{2}
$$
N以下で最大のa_n
素直に不等式を立て、$n$について解き、一般項に代入すればいい。
$$
a_n\le N
$$
として
$$
\frac{3^n - 1}{2}\le N
$$
となるから
$$
3^n\le2N+1
$$
片々底が3の対数をとって
$$
n\le\log_3{(2N+1)}
$$
最大の$n$なので、床関数をとるとよい
$$
n_{max} = \lfloor \log_3{(2N+1)} \rfloor
$$
さて、これを一般項に代入して
$$
a_{n_{max}}=\frac{3^{\lfloor \log_3{(2N+1)} \rfloor} - 1}{2}
$$
テスト。Ruby だが知らなくても読めるだろう。
irb(main):001> def m(n) = (3 ** (Math.log(2 * n + 1, 3).floor) - 1) / 2
=> :m
irb(main):002> m(40)
=> 40
irb(main):003> m(50)
=> 40
irb(main):004> m(5)
=> 4
irb(main):005> m(120)
=> 40
irb(main):006> m(121)
=> 121
irb(main):007> m(60)
=> 40
irb(main):008> m(1250)
=> 1093
これでキレイな shellsort が書けるぞ
参考
- 柴田望洋. (2025). 新・明解Pythonで学ぶアルゴリズムとデータ構造 第2版: （新・明解） (pp. 200-205). SBクリエイティブ. Retrieved from http://books.google.co.kr/books?id=XLKaEQAAQBAJ&dq=isbn:978-4-8156-3721-7&hl=&source=gbs_api