名古屋工業大学 工学研究科 情報工学専攻 2014年8月実施 問題22 情報科学 II

标签：

• 名古屋工业大学
• 快速排序
• 划分操作
• 算法复杂度
• 递推关系的复杂度分析

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

II　$N$ 個の相異なる自然数値が配列 $A$ として与えられるとする（$N>1$）。このとき，配列の値を昇順にソートするアルゴリズムの擬似コードを以下に示す。

1:  int A[0..N-1];

2:  sort(A, low, high) {
3:      if (low < high) {
4:          x = A[low];
5:          i = low; j = high;
6:          while (i <= j) {
7:              while (A[i] < x) i++;
8:              while (A[j] > x) j--;
9:              if (i <= j) {
10:                 swap(A, i, j);
11:                 i++; j--;
12:             }
13:         }
14:         /* 時点 P */
15:         sort(A, low, j);
16:         sort(A, i, high);
17:     }
18: }

この擬似コードは，sort(A, 0, N-1) を実行することで，配列 $A$ 中の値が昇順にソートされる。なお，擬似コード中で使われている手続き swap は以下の処理を行うものとする。

• swap(A, a, b)：配列 $A$ における $A[a]$ の値と $A[b]$ の値を入れ替える。

このとき，次の (1)〜(4) の問いについて答えよ。

(1) この擬似コードで実現されているソーティングアルゴリズムの名前を答えよ。

(2) $N=10$ とし，sort(A, 0, N-1) を実行することを考える。配列 $A$ の初期値が以下のとおりであるとする。

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
18	21	9	13	4	53	19	38	24	6

このとき，擬似コードの実行が初めて時点P（14行目）に到達したときにおける配列 $A$ の内容を書け。

(3) いま，上記の擬似コードの4行目を以下の命令に書き換える。

4:  x = median(A, low, high);

ここで，関数 median は以下の処理を行うものとする。

• median(A, a, b)：$b-a=m-1\ (m\ge1)$ であるような引数 $a,b$ に対して，$A[a],A[a+1],\ldots,A[b]$ の中から $\lceil m/2\rceil$ 番目に小さい値を返す。ただし，天井記号 $\lceil x\rceil$ は実数 $x$ 以上の値を持つ最小の整数を表すものとする。

median(A, a, b) の実行時間が $\Theta(m)$ であるとする。このとき，上述の書き換えを行った擬似コードにより実現されるアルゴリズムの最悪時実行時間を $\Theta$ 記法を用いて書け。

(4) (3) で示した書き換えを行わなかった場合を考える。このとき，入力配列 $A$ の要素数を $n$ として，擬似コードにより実現されるアルゴリズムの最悪時実行時間を $\Theta$ 記法を用いて書け。また，実行時間が漸近的に最悪となる入力配列 $A$ はどのようなものか，理由とともに説明せよ。

题目描述

II　假设数组 $A$ 给出 $N$ 个互不相同的自然数（$N>1$）。下面给出将数组元素按升序排序的算法伪代码。

1:  int A[0..N-1];

2:  sort(A, low, high) {
3:      if (low < high) {
4:          x = A[low];
5:          i = low; j = high;
6:          while (i <= j) {
7:              while (A[i] < x) i++;
8:              while (A[j] > x) j--;
9:              if (i <= j) {
10:                 swap(A, i, j);
11:                 i++; j--;
12:             }
13:         }
14:         /* 时点 P */
15:         sort(A, low, j);
16:         sort(A, i, high);
17:     }
18: }

执行 sort(A, 0, N-1) 后，数组 $A$ 中的值按升序排列。伪代码中的过程 swap 执行以下处理。

• swap(A, a, b)：交换数组 $A$ 中 $A[a]$ 与 $A[b]$ 的值。

回答下列 (1) 至 (4) 问。

(1) 写出该伪代码实现的排序算法名称。

(2) 令 $N=10$，考虑执行 sort(A, 0, N-1)。设数组 $A$ 的初值如下。

A[0]	A[1]	A[2]	A[3]	A[4]	A[5]	A[6]	A[7]	A[8]	A[9]
18	21	9	13	4	53	19	38	24	6

写出伪代码执行首次到达时点 P（第14行）时数组 $A$ 的内容。

(3) 将上述伪代码的第4行改为以下指令。

4:  x = median(A, low, high);

其中函数 median 执行以下处理。

• median(A, a, b)：对于满足 $b-a=m-1\ (m\ge1)$ 的参数 $a,b$，从 $A[a],A[a+1],\ldots,A[b]$ 中返回第 $\lceil m/2\rceil$ 小的值。上取整符号 $\lceil x\rceil$ 表示不小于实数 $x$ 的最小整数。

设 median(A, a, b) 的运行时间为 $\Theta(m)$。请用 $\Theta$ 记法写出修改后的伪代码所实现算法的最坏运行时间。

(4) 考虑没有进行第 (3) 问修改的情况。设输入数组 $A$ 的元素数为 $n$，请用 $\Theta$ 记法写出该算法的最坏运行时间，并说明什么样的输入数组 $A$ 会使运行时间在渐近意义下最坏，以及相应理由。

Kai

(1)

基準値を用いて配列を二分し、各部分を再帰的に整列しているので、

$$\boxed{\text{クイックソート}}$$

である。

(2)

最初の呼出しでは $x=A[0]=18$ である。

• $A[0]=18$ と $A[9]=6$ を交換する。
• 左側では $A[1]=21$ で止まり、右側では $18$ より大きい値を飛ばして $A[4]=4$ で止まるので、$A[1]$ と $A[4]$ を交換する。
• その後、$i=4,j=3$ となって反復が終了する。

したがって、最初の時点 P における配列は

$$\boxed{[6,4,9,13,21,53,19,38,24,18]}$$

である。

(3)

基準値は中央順位の値である。分割後の部分配列の大きさを $n_L,n_R$ とすると、要素が相異なることから

$$n_L+n_R\le n,\qquad \max(n_L,n_R)\le \lceil n/2\rceil+1$$

である。median は $O(n)$ であり、分割処理そのものは $\Theta(n)$ である。したがって再帰の深さは $\Theta(\log n)$、各再帰レベルの処理量は $\Theta(n)$ なので、

$$\boxed{T(n)=\Theta(n\log n)}$$

である。

(4)

先頭要素 A[low] が基準値である。各部分配列でこの値が最小値になると、分割後の大きさが $0$ と $n-1$ になり、

$$T(n)=T(n-1)+\Theta(n)$$

となる。したがって、

$$\boxed{T(n)=\Theta(n^2)}$$

である。この状況を生じる入力の例は、相異なる値が昇順または降順に並んだ配列である。特に昇順の場合、各再帰呼出しでも先頭要素が最小値となり、部分配列が一要素ずつしか縮まない。

Reference

• 公式原題（公式サイトの保存版）