🔙 Back to Top
こんなのがあった.
シェルソートの話をします。[..]
シェルソートの計算量の導出に関する証明について云々書いてあった. というわけで証明を考えてみた.
以下ネタバレ.
シェルソートの動画
ある位置にいる人が前に出てきて 「あろっとおーにー」とか「あろっとそーしー」みたいなことを言う. これはギャップに相当する数字を言ってるんだと思う. たぶん. これを聞くとその人よりもインデックスが \(k\) だけ低い人が出てきて、ペアで大小比較を行う. 逆転してたならスワップが行われ、その時に限りさらに \(k\) だけ低い人を呼び、大小比較を行う.
補題 0
長さがともに \(r\) 以上ある2つの数列があり、
- \(x = (x_1, \ldots, x_n, x_{n+1}, \ldots, x_{n+r})\)
- \(y = (y_1, \ldots, y_r, y_{r+1}, \ldots, y_m)\)
今
- 条件 \(P(x, y)\): \(i=1,2,\ldots,r\) 全てについて \(y_i \leq x_{n+i}\) が成立
を仮定する. \(x, y\) をそれぞれ昇順にソートして得た数列を
- \(x' = (x_1', \ldots, x_n', x_{n+1}', \ldots, x_{n+r}')\)
- \(y' = (y_1', \ldots, y_r', y_{r+1}', \ldots, y_m')\)
とするとこれらについて条件 \(P(x', y')\) が成立している.
証明
\(y_1'\) に注目する. \(y_1' = \min \{ y_1, y_2, \ldots, y_m \}\) であるので、 \[y_i \geq y_1'\] である. 更に \(P(x,y)\) より、 \[x_{n+i} \geq y_i \geq y_1' ~~(i=1,2,\ldots,r)\] というわけで、数列 \(x\) に於いて少なくとも \(r\) 個は \(y_1'\) より大きい数がある. \(x\) のソートを考えると、 \[x'_{n+1} \geq y_1'\] が分かる. なぜなら \(x'_{n+1}\) という数字はソートした後の数列の top \(r\) の数であり、\(r\) 個以上は \(y_1'\) より大きい数が含まれるから.
というわけで、\(P(x', y')\) において \(x'_{n+1} \geq y_1'\) (つまり \(i=1\) の場合) だけは示された.
\(y_2'\) 以降も同様. これより大きな数が数列 \(x\) に \(r-1\) 個は少なくともあるので〜って言えば良い.
補題 1
略
証明
数列
- \(a = (a_1, a_2, \ldots, a_m)\)
が既に \(x\)-sort 済みだとする. すなわち、
- 条件 \(Q_x(a)\): \(\forall i, a_i \leq a_{i+x}\)
これが成立しているとする. 今から \(a\) を \(y\)-sort することを考える. \(y\)-sort するとはつまり、\(a\) から \(y\) 個の部分列
- \(\alpha_1 = (a_1, a_{1+y}, \ldots, a_{-})\)
- \(\alpha_2 = (a_2, a_{2+y}, \ldots, a_{-})\)
- \(\vdots\)
- \(\alpha_y = (a_y, a_{y+y}, \ldots, a_{-})\)
を取り出しそれらを独立にソートし、
- \(\alpha_1' = (a_1', a_{1+y}', \ldots, a_{-}')\)
- \(\alpha_2' = (a_2', a_{2+y}', \ldots, a_{-}')\)
- \(\vdots\)
- \(\alpha_y' = (a_y', a_{y+y}', \ldots, a_{-}')\)
を得て、
- \(a' = (a_1', a_2', \ldots, a_y', \ldots, a_m')\)
を構成すること. \(a'\) が \(y\)-sort 済みなのは自明なので、\(Q_x(a')\) を示せばよい.
\(\alpha_i\) と補題 0 を睨めば自明. すなわち、
\(a_i'\) と \(a_{i+x}'\) の大小比較を確かめる. インデックスの \(i\) 及び \(i+x\) を \(y\) で割った余りを見ることで、それらが どの部分列 \(\alpha_k\) に属するかが分かる.
- ともに同じ \(\alpha_k\) に属するとき
- 各 \(\alpha_k'\) はソートされるので、 \(a_i' \leq a_{i+x}'\)
- \(a_i'\) は \(\alpha_{k_1}\) に、 \(a_{i+x}'\) は \(\alpha_{k_2}\) に属するとき
- ソート前はこんな感じ:
- \(\alpha_{k_1} = (\ldots, a_{i-y}, a_i, a_{i+y}, \ldots)\)
- \(\alpha_{k_2} = (\ldots, a_{i-y+x}, a_{i+x}, a_{i+y+x}, \ldots)\)
- \(a\) は \(x\)-sorted なので、
- \(a_{i-y} \leq a_{i-y+x}\)
- \(a_{i} \leq a_{i+x}\)
- \(a_{i+y} \leq a_{i+y+x}\)
- 前後しか書いてないけど、\(\alpha_{k_1}\) の前半と \(\alpha_{k_2}\) の後半で \(P\) が成立してることが分かる
- ソートする
- 補題 0 より \(\alpha_{k_1}', \alpha_{k_2}'\) で \(P\) が成立してる
- 即ち \(a_i' \leq a_{i+x}'\)
全ての \(i\) についてこれが言えるので、結局 \(a'\) も \(x\)-sort 済みであることが分かった.