東北大学 工学研究科 電気・情報系 2019年3月実施 問題4 情報基礎2
Author
祭音Myyura
Description
日本語版
長さ
- 手続き
は、もし の場合に 、それ以外の場合に を返す. - 手続き
は、配列 の 番目と 番目の要素を入れ替える.ただし、もし なら配 列 は変化しない.
手続き
以下の問に答えよ.
(1) 上記条件を満たす整列アルゴリズムに対する計算量の漸近的下界を
(2) Fig. 4(a) に示す整列アルゴリズム Alg1 の疑似コードを考える.手続き
(3) Fig. 4(b) に示す整列アルゴリズム A1g2 について、手続き又の総呼び出し回数が
(4) Fig. 4((c)) に示す整列アルゴリズム A1g3 の疑似コードを考える.ただし、Fig. 4((c)) 中に示す手続き
- (a) Alg3 の基本戦略と処理の概要を言葉で簡潔に説明せよ.
- (b) 配列
の初期値を とする. Alg3 の 6 行目および 19 行目にある手続き又の実行直後に毎回配列 の値を表示することを考える.配列 の値を表示される順番に全て示せ. - ((c)) Alg3 の計算量を
記法を用いて示せ.
English Version
Every element in an array
- The procedure
returns if , and 0 otherwise. - The procedure
swaps the -th and -th elements in the array , where the array is unchanged if .
We consider algorithms for sorting the real numbers in the array
Answer the following questions.
(1) Give the asymptotic lower bound of the computational complexity in big
(2) Consider the pseudocode for the sorting algorithm Alg1 shown ni Fig. 4(a). Give the number of calls to the procedure
(3) Following the notation of the pseudocode shown in Fig. 4(a), give an appropriate pseudocode by filling ( A ) , ( B ) , and ( C ) of the sorting algorithm Alg2 shown in Fig. 4(b) so that the total number of calls to the procedure
(4) Consider the pseudocode for the sorting algorithm Alg3 shown in Fig. 4((c)), where a procedure
- (a) Succinctly describe the fundamental strategy and an outline of the process of Alg3 in words.
- (b) Suppose that the initial values of the array
are . We consider displaying the values of the array every time right after the procedure at line 6 and line 19 in Alg3 is performed. Show all the values of the array in the order in which they are displayed. - ((c)) Give the computational complexity of Alg3 in big
notation.
Figs
fig. 4(a)
Alg1 (N):
for i := 1 to N-1 do
for j := 2 to N-i+1 do
if P(j, j-1) = 1 then
Q (j,j-1)
endif
endfor
endfor
fig. 4(b)
Alg2 (N):
for i := 1 to N-1 do
k := i
for j := i+1 to N do
if ( A ) then
( B )
endif
endfor
( C )
endfor
fig. 4((c))
Alg3 (N):
for i := 1 to N do
R(N-i+1, N)
endfor
for i := 1 to N-1 do
Q(1, N-i+1)
R(1, N-i)
endfor
R(i, m):
k := i
while k <= m do
j := k
k := k*2
if k <= m then
if k+1 <= m and P(k, k+1) = 1 then
k := k+1
endif
if P(j, k) = 1 then
Q(j, k)
endif
endif
endwhile
Kai
(1)
(2)
Hint: Bubble Sort
In the worst-case (elements of the array
(3)
Hint: Selection Sort
- ( A ): P(j, k)
- ( B ): k = j
- ( C ): Q(i, k)
(4)
Hint: Heap Sort
(a)
Alg3 first convert the array