基本情報技術者試験の公開問題を解こう！（令和5年度・科目B）（3）「整列プログラムで実行される配列の値の変化を求める」

基本情報技術者試験の令和5年度の公開問題（科目B）を解いてみよう。

解答群
ア 　1 2 3 4 5
イ 　1 2 3 5 4
ウ　 2 1 3 4 5
エ 　2 1 3 5 4

この問題は、クイックソートのようなアルゴリズムの動作を理解することがポイントである。

ソートの流れ

1. ピボットの選択:
   pivot ← data((first + last) ÷ 2 の商) なので、
   • 配列 data = {2, 1, 3, 5, 4} の first=1 と last=5 を考えると、
   • (1+5)÷2 = 3 で、3 番目の要素は 3 なので、pivot = 3 となる。
2. 比較・交換:
   • 配列の左側 (i) から、pivot より小さいものを探す。
   • 配列の右側 (j) から、pivot より大きいものを探す。
   • 条件を満たしたら入れ替え、i を進め、j を戻す。
3. 分割と再帰:

• ピボットを基準に分け、再帰的に同じ処理を繰り返す。

本問の実行結果

sort(1, 5) の流れ（※ /*** α ***/ に注目）

1. 呼び出し：sort(1, 5)
2. pivot = data[(1+5) ÷ 2] = data[3] = 3
3. i = 1, j = 5

iとjを動かす

iの動き：

• data[1] = 2 < 3 → i = 2
• data[2] = 1 < 3 → i = 3
• data[3] = 3 == 3 → 止まる

jの動き：

• data[5] = 4 > 3 → j = 4
• data[4] = 5 > 3 → j = 3
• data[3] = 3 == 3 → 止まる

→ i = 3, j = 3 → i ≥ j なのでループ終了する。

→ /*** α ***/ に到達！

この時点での data の中身

iとjは動いたが、値の入れ替え（交換）は一度も行われていない。

つまり、dataの内容は、 まだ最初のままである。

解答群の中で一致するのは、 エ (2 1 3 5 4) となる。