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

●問 (クイックソート)

データ列 ７, ５, ２, １, ３ を配列に格納して，授業で扱った(教科書の)
クイックソートで値を小さい順に並べ替える．

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

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

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

●答 (クイックソート)

(1)

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

(2)

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

[解説]

上記の解答 (1) の系列は，教科書のクイックソートの関数 qsort(p, n) の
呼び出し木(下図)を先行順に走査して得られる．

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

教科書 p.39 の partition() では，分割対象の部分配列 a[p..q] の先頭要素 a[p] を
分割の基準値として使うことに注意する．上の例では
実行前の配列から基準値７，結果の1行目の左側の部分配列から基準値３，
結果の2行目先頭の部分配列から基準値１，結果の4行目中央の部分配列から基準値５，
がそれぞれ選ばれる．

なお，この解答では，手作業での実行を考えやすくするため，
配列が必ず二つの部分に分かれるように，教科書の qsort() を変更している．
具体的には，教科書 p.39 の再帰呼び出し qsort(a, p, j) を qsort(a, p, i-1)
に変えた．元のままの場合，呼び出し (１,１) が (１,０) に変わる．
これは，配列の a[1] から a[2] の範囲が，空列，a[1]，a[2] の範囲の
三つの部分に分かれることを意味する．

上記の解答 (2) では，関数 qsort(p, q) の p < q の場合に
(つまり，整列対象の要素数が2以上で，呼び出しの木の葉以外の節点で)
関数の実行直前と実行直後での配列の中身を示した．
整列対象の要素数が2以上の場合，整列対象の先頭要素を基準値とする値の大小で
配列を2分割し，前半部分と後半部分をそれぞれクイックソートで再帰的に整列する．

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

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