━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題12
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (マージソート)

データ列 7, 5, 2, 1, 3 を配列に格納して，授業で扱った(教科書の)
マージソートで値を小さい順に並べ替える．

(1) 関数 msort(p, n) の呼び出し順を，各呼び出しでの実引き数の対 (p, n) の
    列として（(1,5), (2,3), (3,1), (4,1) などの形式で）表せ．
    ここで，p は配列の開始位置を，n は要素数を表す．

(2) 配列の変化を(授業で扱ったのと同じ形式で)示せ．

──────────────────────────────────────

●答 (マージソート)

(1)

(１,５) (１,２) (１,１) (２,１) (３,３) (３,１) (４,２) (４,１) (５,１)

(2)

実行前
[７, ５, ２, １, ３]
途中結果
[７, ５][２, １, ３]
[７][５][２, １, ３]
[５, ７][２, １, ３]
[５, ７][２][１, ３]
[５, ７][２][１][３]
[５, ７][２][１, ３]
[５, ７][１, ２, ３]
[１, ２, ３, ５, ７]

［解説］

再帰関数の呼び出し順を考えるには，呼び出しの木を使うとよい．
これは，実引き数の組を節点とし，呼び出す引き数の組を子とする木である．
この木を先行順(深さ優先順)に走査すると，呼び出し順の系列が得られる．
上記の解答 (1) の系列は，教科書のマージソートの関数 msort(p, n) の
呼び出しの木(下図)を先行順に走査して得られる．

           (１,５)
          ／     ＼
    (１,２)        (３,３)
     ／ ＼          ／ ＼
(１,１) (２,１) (３,１) (４,２)
                         ／ ＼
                    (４,１) (５,１)

上記の解答 (2) では，関数 msort(p, n) の整列対象の要素数 n が
2以上の場合に(つまり，呼び出しの木の葉以外の節点で)，
関数の実行直前と実行直後での配列の中身を示した．
n≧2 の場合，整列の開始位置 p から n 要素の部分配列を前半部分と後半部分に分け，
それぞれをマージソートで再帰的に整列して，結果をマージする．

教科書のアルゴリズムでは分割時の前半の長さは n を2で割った商なので，
n が奇数なら後半より長さが1短くなる．左右の長さを入れ替えると動作は変わるが，
どちらの分割方法でも呼び出し木は平衡木になるので，同じ計算量で整列できる．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/