名古屋大学 情報学研究科 複雑系科学専攻 2018年8月実施 情3

标签：

• Nagoya-University
• Partitioning
• Quick-Select
• Divide-and-Conquer

Author

祭音Myyura

Description

相異なる $n$ 個の自然数を、インデックス $1$ から $n$ の一次元配列 $A$ に格納する。
$1\le k\le n$ に対し、列中の $k$ 番目に小さい値を返す関数 k_th を、次の関数 partition を用いて作る。

partition(A,i,j) は、$i=j$ なら $i$ を返す。$i<j$ なら pivot = A[j] とし、区間 $A[i],\ldots,A[j]$ を並べ替えて、pivot が格納されたインデックス $p$ を返す。返却時には

$$A[i],\ldots,A[p]\le \mathrm{pivot}, \qquad A[p],\ldots,A[j]\ge \mathrm{pivot}$$

が成り立つ。

手続き `partition(A,i,j)`
 1. もし i と j が等しければ、i を返し、手続きを終了する。
 2. 変数 pivot に A[j] の値を代入する。
 3. 変数 id に i の値を代入する。
 4. 変数 ip に i の値を代入する。
 5. 繰り返し begin
 6.     もし id の値と j の値が等しければ、繰り返しを終了する。
 7.     もし A[id] の値が pivot の値以下であれば、
 8.         begin
 9.             A[ip] の値と A[id] の値を交換する。
11.              ip + 1 の値を ip に代入する。
12.          end
13.      id + 1 の値を id に代入する。
14.  繰り返し end
15.  A[ip] の値と A[j] の値を交換する。
16.  ip の値を返し、手続きを終了する。

[1] $n=8$ の配列

インデックス	1	2	3	4	5	6	7	8
$B$	50	10	80	30	70	20	40	60

に対して partition(B,3,7) を実行する。id、ip または配列 $B$ に対する操作が行われる行番号と、その操作後の状態をすべて示し、返り値も答えよ。見かけ上、配列が変化しない交換も省略しないものとする。

[2] 配列 $A$ が次を満たすとする。

• インデックスが $i$ より小さい全要素は、インデックスが $i$ 以上の全要素より小さい。
• インデックスが $j$ より大きい全要素は、インデックスが $j$ 以下の全要素より大きい。

このとき partition(A,i,j) が $p$ を返したなら、配列 $A$ における $p$ 番目に小さい自然数を求め、その理由を述べよ。

[3] 問 [2] の条件の下で $i\le k\le j$ とする。partition(A,i,j) が $p$ を返したとき、

1. $p>k$ なら、$k$ 番目に小さい自然数はどのインデックス範囲にあるか。
2. $p<k$ なら、$k$ 番目に小さい自然数はどのインデックス範囲にあるか。

[4] k_th(A,1,n,k) が $k$ 番目に小さい自然数を返すように、次の空欄を埋めよ。

手続き k_th(A,i,j,k)

1. 変数 p に partition(A,i,j) が返す値を代入する。
2. もし（ア）であれば、（イ）を返し、手続きを終了する。
3. もし（ウ）であれば、（エ）を返し、手続きを終了する。
4. もし（オ）であれば、（カ）を返し、手続きを終了する。

Kai

[1]

pivot = B[7] = 40 である。

• id=3：$80>40$ なので交換せず、id を 4 にする。
• id=4：$30\le40$ なので $B[3]$ と $B[4]$ を交換し、ip を 4 にする。
• id=5：$70>40$ なので交換しない。
• id=6：$20\le40$ なので $B[4]$ と $B[6]$ を交換し、ip を 5 にする。
• id=7=j で反復を終え、$B[5]$ と $B[7]$ を交換する。

行番号	id の値	ip の値	配列 $B$ の要素の並び
3	3	未定	50 10 80 30 70 20 40 60
4	3	3	50 10 80 30 70 20 40 60
12	4	3	50 10 80 30 70 20 40 60
9	4	3	50 10 30 80 70 20 40 60
10	4	4	50 10 30 80 70 20 40 60
12	5	4	50 10 30 80 70 20 40 60
12	6	4	50 10 30 80 70 20 40 60
9	6	4	50 10 30 20 70 80 40 60
10	6	5	50 10 30 20 70 80 40 60
12	7	5	50 10 30 20 70 80 40 60
14	7	5	50 10 30 20 40 80 70 60

したがって、

$$\boxed{\operatorname{partition}(B,3,7)=5}$$

であり、終了時の配列は

$$\boxed{(50,10,30,20,40,80,70,60)}$$

である。

[2]

partition の終了時には

$$A[p]=\mathrm{pivot}$$

であり、自然数は相異なるので、

$$A[q]<A[p]\quad(i\le q<p),\qquad A[q]>A[p]\quad(p<q\le j)$$

となる。

さらに仮定より、

$$A[q]<A[p]\quad(q<i),\qquad A[q]>A[p]\quad(q>j)$$

である。したがって $A[p]$ より小さい要素はちょうど $p-1$ 個である。

よって、$p$ 番目に小さい自然数は

$$\boxed{A[p]}$$

である。これは partition 呼出し前の pivot、すなわち元の $A[j]$ の値でもある。

[3]

問 [2] より、$A[p]$ は配列全体で $p$ 番目に小さい。

1. $p>k$ のとき、$k$ 番目に小さい自然数は

   $$\boxed{i\le q\le p-1}$$

   の範囲にある。

2. $p<k$ のとき、$k$ 番目に小さい自然数は

   $$\boxed{p+1\le q\le j}$$

   の範囲にある。

[4]

空欄は次の通りである。

空欄	解答
（ア）	$p=k$
（イ）	$A[p]$
（ウ）	$p>k$
（エ）	k_th(A,i,p-1,k)
（オ）	$p<k$
（カ）	k_th(A,p+1,j,k)

したがって、完成した手続きは

手続き k_th(A,i,j,k)

1. p に partition(A,i,j) の返り値を代入する。
2. もし p = k であれば、A[p] を返す。
3. もし p > k であれば、k_th(A,i,p-1,k) を返す。
4. もし p < k であれば、k_th(A,p+1,j,k) を返す。

となる。ここで $k$ は配列全体における順位であり、再帰呼出しでもインデックスを保持するため、右側を探索するときも $k-p$ などへ変換する必要はない。