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

増加列ブロック数を $s_1$、減少列ブロック数を $s_2$ とすると、 これらはそれぞれ減少箇所、増加箇所より 1 ずつ大きい。 減少箇所、増加箇所はもちろん同じ場所にはなく、 よってそれらの和は $(N-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}$ ならば $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}

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


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

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


命題 7

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


次へ: 9 方法 B の整列化の例 上へ: sort1 前へ: 7 並べ直しの具体例
竹野茂治＠新潟工科大学
2006年2月24日