跳到主要内容

名古屋工業大学 工学研究科 情報工学専攻 2015年度 計算機ソフトウェア（データ構造とアルゴリズム）

标签：

Author​

GPT-5.6 Sol, 祭音Myyura

Description​

設問 II について答えよ。NN 個の相異なる自然数値が配列 A として与えられる（N>1N>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(A,a,b) は、配列 A の A[a] と A[b] を入れ替える手続きである。

(1)​

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

(2)​

N=10N=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]
18219134531938246

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

(3)​

4 行目を次の命令に書き換える。

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

median(A,a,b) は、b−a=m−1b-a=m-1（m≥1m\ge1）である引数 a,ba,b に対して、

A[a],A[a+1],…,A[b]A[a],A[a+1],\ldots,A[b]

の中から ⌈m/2⌉\lceil m/2\rceil 番目に小さい値を返す。ここで、天井記号 ⌈x⌉\lceil x\rceil は実数 xx 以上の最小の整数を表す。median(A,a,b) の実行時間は O(m)O(m) であるとする。

この書き換えを行った擬似コードによるアルゴリズムの最悪時実行時間を、Θ\Theta 記法を用いて書け。

(4)​

(3) の書き換えを行わない場合を考える。入力配列 A の要素数を nn として、アルゴリズムの最悪時実行時間を Θ\Theta 記法で書け。また、実行時間が漸近的に最悪となる入力配列 A がどのようなものか、理由とともに説明せよ。

Kai​

(1)​

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

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

である。

(2)​

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

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

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

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

である。

(3)​

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

nL+nR≤n,max⁡(nL,nR)≤⌈n/2⌉+1n_L+n_R\le n,\qquad \max(n_L,n_R)\le \lceil n/2\rceil+1

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

T(n)=Θ(nlog⁡n)\boxed{T(n)=\Theta(n\log n)}

である。

(4)​

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

T(n)=T(n−1)+Θ(n)T(n)=T(n-1)+\Theta(n)

となる。したがって、

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

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

検算​

与えられた擬似コードの最初の分割をプログラムで実行し、時点 P で A=[6,4,9,13,21,53,19,38,24,18]、i=4、j=3 となることを確認した。また、8 要素までの全順列が正しく整列されること、および昇順入力では分割処理量が 2+3+⋯+n=Θ(n2)2+3+\cdots+n=\Theta(n^2) となることを確認した。

本页目录