クイックソートアルゴリズムのトレース

■ 解き方の方針 αが最初に実行されるのは、最初のsort(1, 5)の分割処理が終わった直後です。後続の再帰呼出しはまだ行われていないので、最初の分割だけを追います。 ■ pivotと初期値 data={2, 1, 3, 5, 4}、first=1、last=5です。したがってpivot=data[(1+5)÷2の商]=data[3]=3、i=1、j=5となります。 ■ 左右からの探索 iの移動: data[1]=2とdata[2]=1は3未満なので、iは1→2→3と進みます。data[3]=3は3未満でないため、i=3で止まります。 jの移動: data[5]=4とdata[4]=5は3より大きいので、jは5→4→3と減ります。data[3]=3は3より大きくないため、j=3で止まります。 ■ 交換の有無と出力 現在はi=3、j=3なので、終了条件i ≥ jが真になります。交換処理へ進まずwhileを抜けるため、配列は初期状態から変化しません。最初のαで出力されるのは 2 1 3 5 4 です。 ■ 正解と誤答の見分け方 したがって、正解は エ です。 整列済みの最終結果を求める問題ではありません。「αを最初に実行したとき」なので、再帰による整列前の配列を答えます。

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