次へ: 9 方法 B の整列化の例 上へ: sort1 前へ: 7 並べ直しの具体例 (PDF ファイル: sort1-2.pdf)

8 方法 B の場合

方法 B の場合は、方法 A のやり方を応用して解くことができる。

この場合、1 回の手順では、5 節で述べたのとは異なり、1 回の配分では元の増加列は減少列へと変化する:

$\begin{displaymath} 1 2 3 4 5 6 \rightarrow \left\{\begin{array}{ll} A_... ... 6 3 1\end{array}\right. \rightarrow (5 4 2), (6 3 1) \end{displaymath}$

もう 1 回これを配分すれば、また増加列へと変わる。

よって、方法 A の場合に偶数回で終了する場合には方法 B でも偶数回で整列化でき、奇数回で終了する場合には、方法 B で同様のことを行なうと降順になってしまうことになる (正確には B 列ではそうではないが少なくとも A 列ではそうなる)。その場合は、もう 1 回、一つの山にだけ配分すれば正しく昇順に直せることになる。

これだけみると、方法 B の方が方法 A より手数がかかりそうに見えるかもしれないが、実際にはそうではない。例えば、丁度逆順の並び ,,...,3,2,1 を考えればわかるが、これは方法 A では最悪の手順数が必要となるが、方法 B なら 1 つの山に配るだけで 1 回で終了する。つまり、方法 B の場合は、増加列ブロック数だけでなく、 減少列ブロック数 によっても最短手順が決まることになる。

増加列ブロック数を、減少列ブロック数をとすると、これらはそれぞれ減少箇所、増加箇所より 1 ずつ大きい。減少箇所、増加箇所はもちろん同じ場所にはなく、よってそれらの和はであるから、

$\begin{displaymath} s_1+s_2 = N+1\end{displaymath}$

(2)

が言える。

なお、減少列ブロック数は、 A 列を逆転 (前後を反対にした列) の増加列ブロック数に等しく、実際の作業でも、実はこの逆転させた列の増加列で考えることになる。

容易にわかるように、減少列ブロック数で考えた場合は、増加列ブロックで考えるのとは逆で、これが方法 A で奇数回で終わるブロック数ならば、方法 B では同じ回数で昇順にでき、方法 A で隅数回で終わるブロック数ならば、方法 B では同じ回数では降順になってしまうのでもう 1 回必要となる。

よって、この場合は、

$\begin{displaymath} \left\{\begin{array}{ll} M^{2J-2}<s_1\leq M^{2J-1} & \mbox{... ...2J-1}<s_1\leq M^{2J} & \mbox{ならば $2J$ 回}\end{array}\right.\end{displaymath}$

となるので、結局 $M^{2J-2}<s_1\leq M^{2J}$ ならば

回となる。同様に考えると結局次が言える。

命題 6

方法 B の場合、

$\begin{displaymath} \left\{\begin{array}{ll} M^{2J-2}<s_1\leq M^{2J} & \mbox{�... ...\leq M^{2J+1} & \mbox{ならば $(2J+1)$ 回} \end{array}\right. \end{displaymath}$

で昇順に直せるので、この小さい方を選択すればよい。

これが最適な回数であることも容易に示される。でそれを説明する。例えば、A 列の 1,2,..., は、方法 B の 1 回の操作では高々 2 つの減少列ブロックからなる。よって、3 つ以上の減少列ブロックを含む A 列の最終形は、方法 B 1 回では元には戻せない。

2 回では高々 4 つの増加列ブロックからなる列になるので、 5 つ以上の増加列ブロックを持つものは方法 B 2 回では元には戻せない。このように考えれば、命題 6 の評価が最適であることがわかる。

命題 7

方法 B の場合、昇順への整列化には最低でも命題 6 の回数だけ必要

次へ: 9 方法 B の整列化の例 上へ: sort1 前へ: 7 並べ直しの具体例

竹野茂治＠新潟工科大学
2006年2月24日