令和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 手を表示)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目大域: 整数型の配列: data ← {2, 1, 3, 5, 4} | data = {2, 1, 3, 5, 4} |
| 2 | 3行目○sort(整数型: first, 整数型: last) | first = 1 last = 5 |
| 3 | 4行目整数型: pivot, i, j | |
| 4 | 5行目pivot ← data[(first + last) ÷ 2 の商] | pivot = 3 |
| 5 | 6行目i ← first | i = 1 |
| 6 | 7行目j ← last | j = 5 |
| 7 | 8行目while (true) | 真 |
| 8 | 9行目while (data[i] < pivot) | 真 |
| 9 | 10行目i ← i + 1 | i = 2 |
| 10 | 9行目while (data[i] < pivot) | 真 |
| 11 | 10行目i ← i + 1 | i = 3 |
| 12 | 9行目while (data[i] < pivot) | 偽 |
| 13 | 12行目while (pivot < data[j]) | 真 |
| 14 | 13行目j ← j - 1 | j = 4 |
| 15 | 12行目while (pivot < data[j]) | 真 |
| 16 | 13行目j ← j - 1 | j = 3 |
| 17 | 12行目while (pivot < data[j]) | 偽 |
| 18 | 15行目if (i ≧ j) | 真 |
| 19 | 16行目繰返し処理を終了する | |
| 20 | 22行目dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/ | |
| 21 | 23行目if (first < i - 1) | 真 |
| 22 | 3行目○sort(整数型: first, 整数型: last) | last = 2 |
| 23 | 4行目整数型: pivot, i, j | |
| 24 | 5行目pivot ← data[(first + last) ÷ 2 の商] | pivot = 2 |
| 25 | 6行目i ← first | i = 1 |
| 26 | 7行目j ← last | j = 2 |
| 27 | 8行目while (true) | 真 |
| 28 | 9行目while (data[i] < pivot) | 偽 |
| 29 | 12行目while (pivot < data[j]) | 偽 |
| 30 | 15行目if (i ≧ j) | 偽 |
| 31 | 18行目data[i]とdata[j]の値を入れ替える | data = {1, 2, 3, 5, 4} |
| 32 | 19行目i ← i + 1 | i = 2 |
| 33 | 20行目j ← j - 1 | j = 1 |
| 34 | 8行目while (true) | 真 |
| 35 | 9行目while (data[i] < pivot) | 偽 |
| 36 | 12行目while (pivot < data[j]) | 偽 |
| 37 | 15行目if (i ≧ j) | 真 |
| 38 | 16行目繰返し処理を終了する | |
| 39 | 22行目dataの全要素の値を要素番号の順に空白区切りで出力する /*** α ***/ | |
| 40 | 23行目if (first < i - 1) | 偽 |
| 41 | 26行目if (j + 1 < last) | 偽 |
| 42 | 24行目sort(first, i - 1) | last = 5 pivot = 3 i = 3 j = 3 |
| 43 | 26行目if (j + 1 < last) | 真 |
| 44 | 3行目○sort(整数型: first, 整数型: last) | first = 4 |
| 45 | 4行目整数型: pivot, i, j | |
| 46 | 5行目pivot ← data[(first + last) ÷ 2 の商] | pivot = 5 |
| 47 | 6行目i ← first | i = 4 |
| 48 | 7行目j ← last | j = 5 |
| 49 | 8行目while (true) | 真 |
| 50 | 9行目while (data[i] < pivot) | 偽 |
| 51 | 12行目while (pivot < data[j]) | 偽 |
| 52 | 15行目if (i ≧ j) | 偽 |
| 53 | 18行目data[i]とdata[j]の値を入れ替える | data = {1, 2, 3, 4, 5} |
| 54 | 19行目i ← i + 1 | i = 5 |
| 55 | 20行目j ← j - 1 | j = 4 |
| 56 | 8行目while (true) | 真 |
| 57 | 9行目while (data[i] < pivot) | 偽 |
| 58 | 12行目while (pivot < data[j]) | 偽 |
| 59 | 15行目if (i ≧ j) | 真 |
| 60 | 16行目繰返し処理を終了する |
出力:2 1 3 5 4, 1 2 3 5 4, 1 2 3 4 5