次へ: 10 方法 A, B の比較 上へ: sort1 前へ: 8 方法 B の場合 (PDF ファイル: sort1-2.pdf)

9 方法 B の整列化の例

ここでは、方法 B の場合の整列化の方法の具体例を紹介する。 8 節でも述べたように、 実際には減少列ブロックではなく、 逆転させた増加列で考える方が自然であるが、それについても説明する。 簡単のため、$M=2$ で考える。

例えば、B 列の初期配列が

6,2,8,3,7,1,5,4

である場合、A 列の最終形は

6,2,4,8,7,1,5,3

であるので、

$$\left\{\begin{array}{lll} 増加列ブロック: & (6), (2 4 8)... ... 2), (4), (8 7 1), (5 3) & \mbox{ 4 個}\end{array}\right.$$

となり、増加列ブロックで行なうと方法 A ならば 3 回で終わるが、 方法 B だと 3 回では降順になってしまうので、 全部を一度ひっくり返すために 4 回かかることになる。

減少列ブロックで考えると、これを統合すると 2 回で一つのブロックにはできるが、 最終的には降順なので、もう一回必要で、3 回かかることになる。

まず、この減少列ブロックの復元を考えてみる。

$$\begin{eqnarray*}&& (6 2) (4) (8 7 1) (5 3) \leftarrow \left\{\begi... ...ox{]} & (ウ) \end{tabular}} \hspace{1zw}(\mbox{A 列の初期状態})\end{eqnarray*}$$

これを B 列で行なってみる。

$$\begin{eqnarray*}&& \raisebox{-8pt}{\tabcolsep=2.5pt\begin{tabular}{rcccccclc}... ...8 \end{array}\right.\\ & \rightarrow & 1 2 3 4 5 6 7 8\end{eqnarray*}$$

ところが、この例では 1 回目に全体を逆転させる手順が入っている。 降順でもいい場合、あるいは降順への整列化の場合への応用も考えると この方法は無駄で、 むしろ最後に全体を逆転させる手順が来る方がよい。

これは A 列で言えば、A 列の最終形を最初に逆転させ、 その増加列ブロックを統合することに他ならない。 今度はその手順を紹介する。 逆転された A 列の最終形 3,5,1,7,8,4,2,6 から開始する。

$$\begin{eqnarray*}&& (3 5) (1 7 8) (4) (2 6) \leftarrow \left\{\begi... ...x{]} & (イ)' \end{tabular}} \hspace{1zw}(\mbox{A 列の初期状態})\end{eqnarray*}$$

これで B 列を整列化する。

$$\begin{eqnarray*}&& \raisebox{-8pt}{\tabcolsep=2.5pt\begin{tabular}{rcccccclc}... ...& \end{array}\right.\\ & \rightarrow & 1 2 3 4 5 6 7 8\end{eqnarray*}$$

これで、回数は変わらずに、逆転は最後に行なうようにすることができる。

この方法ならば、コンピュータのプログラム化も容易で、 増加列ブロックの統合部分を作ってしまえば、 それを方法 A でも方法 B でも利用することができることになる。

実は、ある A 列に対する方法 A の手順列が、$e_1$, $e_2$, ...$e_K$ の場合、 それと同じ A 列を用いた方法 B の手順列は、 $\bar{e_1}$, $\hat{e_2}$, $\bar{e_3}$, $\hat{e_4}$, ...となることが 容易示される。ここで、$\bar{e}$ は $e$ の置く位置を反転させたもの、 すなわち、$A_j$ の山へ置くことを $A_{M-j+1}$ の山へ置くことと 読み変えたものであり、 $\hat{e}$ は $e$ の前後を逆転させたもの、 すなわち、手順の前後を入れかえたものである。

よって、増加列ブロックの統合ルーチンによる手順列を 適当に反転、逆転させれば方法 A でも方法 B でも、 整列化手順列の生成ができることになる。

次へ: 10 方法 A, B の比較 上へ: sort1 前へ: 8 方法 B の場合