うごく基本情報

令和5年度 公開問題 科目B 問3

再帰 ・ 整列 ・ 大域変数 ・ トレース

次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
次の手続 sort は,大域の整数型の配列 data の,引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで,first< last とする。手続 sort を sort(1, 5) として呼び出すと,/*** α ***/ の行を最初に実行したときの出力は“[ ]”となる。

大域: 整数型の配列: data ← {2, 1, 3, 5, 4}

○sort(整数型: first, 整数型: last)
  整数型: pivot, i, j
  pivot ← data[(first + last) ÷ 2 の商]
  i ← first
  j ← last
  while (true)
    while (data[i] < pivot)
      i ← i + 1
    endwhile
    while (pivot < data[j])
      j ← j - 1
    endwhile
    if (i ≧ j)
      繰返し処理を終了する
    endif
    data[i]とdata[j]の値を入れ替える
    i ← i + 1
    j ← j - 1
  endwhile
  dataの全要素の値を要素番号の順に空白区切りで出力する  /*** α ***/
  if (first < i - 1)
    sort(first, i - 1)
  endif
  if (j + 1 < last)
    sort(j + 1, last)
  endif
答え
ア1 2 3 4 5
イ1 2 3 5 4
ウ2 1 3 4 5
エ2 1 3 5 4

出典:令和5年度 基本情報技術者試験 科目B 公開問題 問3

正解と解説を見る

正解:エ

ポイント:クイックソートの1回目の分割:左から pivot 以上、右から pivot 以下を探して入れ替え、i と j が出会ったら終わり。

sort(1, 5) を呼んだとき、αの行で最初に出力される内容を求めます。data={2, 1, 3, 5, 4} です。
pivot=data[(1+5)÷2 の商]=data[3]=3。i=1、j=5 から始めます。
・左から:data[1]=2 < 3 なので i=2、data[2]=1 < 3 なので i=3、data[3]=3 は 3 未満でないので止まる(i=3)。
・右から:3 < data[5]=4 なので j=4、3 < data[4]=5 なので j=3、3 < data[3]=3 ではないので止まる(j=3)。
・i ≧ j(3 ≧ 3)なので、入れ替えずにループを終了します。
この時点で data は最初のまま {2, 1, 3, 5, 4} なので、αで「2 1 3 5 4」が出力されます(エ)。
よくある間違い:整列が全部終わった結果「1 2 3 4 5」(ア)を答える。問われているのは最初の出力で、このあと再帰呼び出しで左右がそれぞれ整列されます。

解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。

正解のプログラムを動かしてみる

sort(1, 5) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 64 手、最初の 60 手を表示)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目大域: 整数型の配列: data ← {2, 1, 3, 5, 4}data = {2, 1, 3, 5, 4}
23行目○sort(整数型: first, 整数型: last)first = 1
last = 5
34行目整数型: pivot, i, j
45行目pivot ← data[(first + last) ÷ 2 の商]pivot = 3
56行目i ← firsti = 1
67行目j ← lastj = 5
78行目while (true)真
89行目while (data[i] < pivot)真
910行目i ← i + 1i = 2
109行目while (data[i] < pivot)真
1110行目i ← i + 1i = 3
129行目while (data[i] < pivot)偽
1312行目while (pivot < data[j])真
1413行目j ← j - 1j = 4
1512行目while (pivot < data[j])真
1613行目j ← j - 1j = 3
1712行目while (pivot < data[j])偽
1815行目if (i ≧ j)真
1916行目繰返し処理を終了する
2022行目dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/
2123行目if (first < i - 1)真
223行目○sort(整数型: first, 整数型: last)last = 2
234行目整数型: pivot, i, j
245行目pivot ← data[(first + last) ÷ 2 の商]pivot = 2
256行目i ← firsti = 1
267行目j ← lastj = 2
278行目while (true)真
289行目while (data[i] < pivot)偽
2912行目while (pivot < data[j])偽
3015行目if (i ≧ j)偽
3118行目data[i]とdata[j]の値を入れ替えるdata = {1, 2, 3, 5, 4}
3219行目i ← i + 1i = 2
3320行目j ← j - 1j = 1
348行目while (true)真
359行目while (data[i] < pivot)偽
3612行目while (pivot < data[j])偽
3715行目if (i ≧ j)真
3816行目繰返し処理を終了する
3922行目dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/
4023行目if (first < i - 1)偽
4126行目if (j + 1 < last)偽
4224行目sort(first, i - 1)last = 5
pivot = 3
i = 3
j = 3
4326行目if (j + 1 < last)真
443行目○sort(整数型: first, 整数型: last)first = 4
454行目整数型: pivot, i, j
465行目pivot ← data[(first + last) ÷ 2 の商]pivot = 5
476行目i ← firsti = 4
487行目j ← lastj = 5
498行目while (true)真
509行目while (data[i] < pivot)偽
5112行目while (pivot < data[j])偽
5215行目if (i ≧ j)偽
5318行目data[i]とdata[j]の値を入れ替えるdata = {1, 2, 3, 4, 5}
5419行目i ← i + 1i = 5
5520行目j ← j - 1j = 4
568行目while (true)真
579行目while (data[i] < pivot)偽
5812行目while (pivot < data[j])偽
5915行目if (i ≧ j)真
6016行目繰返し処理を終了する

出力:2 1 3 5 4, 1 2 3 5 4, 1 2 3 4 5

サイトで、1行ずつ予想しながら動かす →