科目B
令和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
答えを選ぶ
出典：令和5年度 基本情報技術者試験 科目B 公開問題 問3（問題文は IPA の公開問題。図・数式・下線などはテキストに直して掲載。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：エ
覚える知識
クイックソートのアルゴリズム
クイックソートは、基準値（ピボット）より小さい要素を左に、大きい要素を右に分け、分けたそれぞれの範囲を再帰的に整列する方法です。
この問題で必要なこと
pivot は data[(1＋5)÷2 の商] = data[3] = 3 です。i は 1 から進み、data[1]=2、data[2]=1 は pivot より小さいので飛ばし、data[3]=3 で止まって i=3 になります。j は 5 から戻り、data[5]=4、data[4]=5 は pivot より大きいので飛ばし、data[3]=3 で止まって j=3 になります。i≧j なので一度も入れ替えずにループを抜け、α では元のままの 2 1 3 5 4 が出力されます。正解はエです。
ひっかけ
アは、整列し終わった状態と取り違えさせる選択肢です。イ・ウは、1 回目の分割で何かが入れ替わると思い込ませます。実際には、最初の i と j が同じ位置で止まるので入れ替えは起きません。