ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

問3 クイックソートの最初の分割の結果

基本情報​技術者試験 令和5年度 公開問題 科目B、全6問のうちの問3。

出典：令和5年度 基本情報技術者試験 公開問題 科目B 問3（プログラムは原本の画像を文字に書き起こし、字下げは 1 段を空白 2 つで表した。空欄は［　　］で表した）

次の記述中の［　　］に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 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. ア1 2 3 4 5
  2. イ1 2 3 5 4
  3. ウ2 1 3 4 5
  4. エ2 1 3 5 4
答えと解説を開く

正解はエです。

sort(1, 5) では、(1 ＋ 5) ÷ 2 の商は 3 なので、pivot ← data[3] ＝ 3 です。i ← 1、j ← 5 から始めます。1 つ目の内側の while は、data[i] が pivot より小さい間 i を進めます。data[1] ＝ 2 ＜ 3 なので i ＝ 2、data[2] ＝ 1 ＜ 3 なので i ＝ 3、data[3] ＝ 3 は 3 より小さくないので i ＝ 3 で止まります。2 つ目の while は、pivot が data[j] より小さい間 j を戻します。3 ＜ data[5] ＝ 4 なので j ＝ 4、3 ＜ data[4] ＝ 5 なので j ＝ 3、3 ＜ data[3] ＝ 3 は偽なので j ＝ 3 で止まります。i ＝ 3、j ＝ 3 で i ≧ j が真なので、入替えをせずに外側の繰返しを終えます。α の行では data がそのまま出力され、2 1 3 5 4 です。このあと sort(1, 2) と sort(4, 5) が呼ばれて、最後に 1 2 3 4 5 になります。正解はエです。

ほかの選択肢が違う理由

  • ア整列が全部終わったあとの並びです。α の行を最初に実行するのは、最初の分割を終えた時点で、まだ前半と後半を並べ替えていません。
  • イ前半の 2 と 1 だけを並べ替えた形です。最初の α の時点では、前半を整列する sort(1, 2) はまだ呼ばれていません。
  • ウ後半の 5 と 4 だけを並べ替えた形です。最初の分割では i と j が 3 の位置で出会い、5 と 4 は入れ替わりません。

仕組み

この手続はクイックソートです。基準値 (pivot) より小さい値を前へ、大きい値を後ろへ分け、前と後ろをそれぞれ同じ手続で整列します。

途中の出力を問う問題では、出力の行に来るまでの i、j、data の変化を表に書いて 1 行ずつ追います。最後の結果と途中の結果を取り違えないことが大事です。

この問に出る言葉