次へ: 7 並べ直しの具体例 上へ: sort1 前へ: 5 必要な回数の評価 (PDF ファイル: sort1-2.pdf)

6 最適解の構成

ここでは、命題 1 の十分性を与える手順を 構成することを考える。すなわち、

$M^{k-1}+1\leq \mbox{(増加列ブロック数)}\leq M^k$ のとき、 $k$ 回の手順で整列化する

ような構成法を考える。このような構成法が見つかれば、 命題 1 より方法 A に関しては明らかにそれが最適な手順となる。

A 列の最終形の増加列ブロックが 2 つである場合をまず考える。 例えばそれが

2,3,5,1,4,6

である場合、 これは、前の (2,3,5) のブロックが $A_1$ で、 後ろの (1,4,6) のブロックが $A_2$ にあったはずで、 これを元の 1 増加列ブロックに直すには、 単純にそれを集めて整列化すればよい。

$$(2 3 5), (1 4 6) \leftarrow \left\{\begin{array}{ll}... ...3 & 4 & 5 & 6\\ A_2 & A_1 & A_1 & A_2 & A_1 & A_2 \end{array}$$

なお、この表の見方は、本来は矢印の方向に (右から左へ) 配分作業は進むのであるが、 今は A 列の最終形から A 列の初期配列に戻すということを考えているので、 それを左から右に書き表した。 以後、このような表現を用いることにする。

今度は、A 列の最終形の増加列ブロックが 3 つの場合を考える。 この場合は一つ前の段階が 2 つの増加列ブロックで、 そこからこれが作られたと考えればよい。

例えばそれが 2,3,5,4,1,6 である場合、 これは、2 回の配分後の 4 ブロックのうち一つが空集合になっていて、 例えば

$$\left\{\begin{array}{lll} (2,3,5) & = & \mbox{1 回目 $A_1$,... ... (1,6) & = & \mbox{1 回目 $A_2$, 2回目 $A_2$}\end{array}\right.$$

であると考えれば、

$$(2 3 5), (4), (1 6) \leftarrow \left\{\begin{array}{... ..., (1 6)\end{array}\right. \leftarrow (2 3 4 5), (1 6)$$

と、一つ前の 2,3,4,5,1,6 の形に復元できることになる。 これは増加列ブロックが 2 つなので、 前と同じようにすれば全体を整列化できる。

$M>2$ の場合も、例えば

$$a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8 \hspace{1zw}(\mbox{各 $a_j$ はそれぞれ増加列ブロック})$$

のように増加列ブロックが 8 つで、$M=3$ の場合、

$$\begin{array}{l} a_1, a_2, a_3, a_4, a_5, a_6, a_7, ... ..., $a_6$ を 整列化した増加列ブロックを意味する})。 \end{array}$$

のようにすれば 3 個の増加列ブロックに復元できる

このようにして、$L$ 個の増加列ブロックのものを、一回戻して $\lceil L/M\rceil$ 個の増加列ブロックにすることができる。

命題 3

A 列の最終列に含まれる増加列のブロック数が $M^k$ 個以下ならば、 $k$ 回の手順で生成でき、その手順は上のように構成可能である。

次へ: 7 並べ直しの具体例 上へ: sort1 前へ: 5 必要な回数の評価