次へ: 4 A 列と B 列 上へ: sort1 前へ: 2 問題設定 (PDF ファイル: sort1-2.pdf)


3 簡単な解

ここでは、まず簡単に思いつく解を一つ紹介する。 例として、$N=16$, $M=2$ で、方法は A の場合で説明する。

  1. 1 回目に、$A_1$ に 8 以下、$A_2$ に 9 以上の番号を配り分け、 それを集める。 すると、手持ちの紙は上半分が 1 から 8, 下半分が 9 から 16 になる (図 1)。
    図 1: 単純な解: 1 回目
    \includegraphics{simple1.eps}

  2. 2 回目の分配では、 それぞれ配分する。その結果は、上から 4 枚ずつ $1\sim 4$, $9\sim 12$, $5\sim 8$, $13\sim 16$ と分けられることになる (図 2)。
    図 2: 単純な解: 2 回目
    \includegraphics{simple2.eps}

  3. 3 回目、4 回目も同様に、それぞれの小ブロックを、 $A_1$ には小さい数、$A_2$ には大きい数となるように 2 つに分けて 分配していく (図 3)。
    図 3: 単純な解: 3, 4 回目
    \includegraphics{simple3.eps}
    その結果、4 回目にすべて 1 枚ずつのブロックに分割され、 上から順に、

    \begin{displaymath} 1,9,5,13,3,11,7,15,2,10,6,14,4,12,8,16 \end{displaymath}

    と並ぶことになる。

この最後の並びは、最初の並びが何であっても上の手順で確実に その並びにできる。

よって、この最後の並びが 1,2,3,..., 16 となるように

\begin{displaymath} { \arraycolsep=2pt \begin{array}{cccccccccccccccc} 1& 9& 5&... ... & (10) & (11) & (12) & (13) & (14) & (15) & (16) \end{array}} \end{displaymath}

という対応をつけて逆に考え、このかっこの方の数字を紙の数字と 見ることで昇順に整列化できることになる。

例えば、上の 1 回目の配分は、 $A_1$ が $1\sim 8$, $A_2$ が $9\sim 16$, すなわち、かっこの数字で言えば

\begin{displaymath} \left\{\begin{array}{ll} A_1: & \{(1),(9),(5),(13),(3),(11)... ... & \{(2),(10),(6),(14),(4),(12),(8),(16)\} \end{array}\right.\end{displaymath}

と分けることに相当する ($\{\}$ 内は順不同)。 これまでの作業をこのように読み変えていけばよい。

ついでに 2,3,4 回目の配分も書き上げると、

と、このように整列化が進むことになる。

しかし、これらの分配は人間がすぐに判定して左右に分けることは難しいので、 コンピュータの音声ガイドなどが必要であると思われる。

この方法だと、 $9\leq N\leq 16$ の場合は今と同じやり方で 4 回で整列化が行なえる。一般の $N$, $M$ の場合は、

\begin{displaymath} M^{K-1}<N\leq M^K \mbox{ ならば $K$ 回で整列化可能}\end{displaymath} (1)

となることが言え、よって必要な回数は $\lceil\log_MN\rceil$ となる ( $\lceil x\rceil$ は $x$ 以上の最小の整数)。

しかし、これはどのような初期配列に対しても同じ回数かかる手順であり、 最適な解ではない。

次へ: 4 A 列と B 列 上へ: sort1 前へ: 2 問題設定
竹野茂治＠新潟工科大学
2006年2月24日