令和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
答えと解説を見る
✓ これが正解エ2 1 3 5 4
解説
最初のα実行時は入替えが起きず、2 1 3 5 4 のままです。
手続 sort は、基準となる値 pivot より小さい要素を前へ、大きい要素を後ろへ分けてから、前後の部分をそれぞれ同じ手続で整列する作りです。αの行は、この分ける作業が1回終わるたびに配列全体を出力します。軸は、最初の呼出し sort(1, 5) でαに着くまでに、どの要素が入れ替わるかを正しく追うことです。
data は {2, 1, 3, 5, 4} です。pivot は data[(1 ＋ 5) ÷ 2 の商]＝data[3]＝3 になります。i は 1 から始まり、data[1]＝2 と data[2]＝1 は 3 より小さいので進み、data[3]＝3 で止まって i＝3 です。j は 5 から始まり、data[5]＝4 と data[4]＝5 は 3 より大きいので戻り、data[3]＝3 で止まって j＝3 です。
ここで i ≧ j が成り立つので、入替えを一度も行わずに外側の繰返しを抜けます。αの行で出力されるのは元のままの 2 1 3 5 4 です。3 より小さい 2 と 1 はすでに前側に、大きい 5 と 4 は後ろ側にあるので、この段階では並べ替える必要がなかったわけです。
再帰呼出しをする整列の問では、何回目の出力を問われているかを確かめ、その時点までに実行された入替えだけを数えると見分けられます。
ほかの選択肢はなぜ違うのか
- ア1 2 3 4 5：1 2 3 4 5 は整列がすべて終わった後の並びです。最初のαの時点では前側と後ろ側をまだ再帰呼出しで処理しておらず、2 と 1、5 と 4 はどちらも元の順のまま残っています。
- イ1 2 3 5 4：1 2 3 5 4 は、前側を処理する sort(1, 2) の中で 2 と 1 が入れ替わった後、2回目のαで出力される並びです。最初のαの時点では、この入替えはまだ起きていません。
- ウ2 1 3 4 5：2 1 3 4 5 は後ろ側の 5 と 4 だけが入れ替わった並びです。このプログラムは前側の sort(1, 2) を先に呼ぶので、前側が整う前に後ろ側だけが整う時点はなく、最初のαでも入替えは起きていません。
出典：令和5年度 基本情報技術者試験 科目B 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）