問題
次の手続 sort は、大域の整数型の配列 data の、引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。ここで、first ＜ last とする。手続 sort を sort(1, 5) として呼び出すと、/*** α ***/ の行を最初に実行したときの出力はどれか。正しい答えを解答群の中から選べ。ここで、配列の要素番号は 1 から始まる。
選択肢
- 11 2 3 4 5
- 21 2 3 5 4
- 32 1 3 4 5
- 42 1 3 5 4
正解
4. 2 1 3 5 4
詳しい解説を見る解説を閉じる
解説
これはクイックソットの分割（パーティション）処理です。最初の sort(1, 5) で data は {2, 1, 3, 5, 4}、pivot は data[(1＋5)÷2 の商]＝data[3]＝3 です。i＝1、j＝5 から開始し、左から pivot 以上になる位置、右から pivot 以下になる位置を探します。i は data[1]=2、data[2]=1 が pivot 未満なので進み、data[3]=3 で止まって i＝3。j は data[5]=4、data[4]=5 が pivot 超なので戻り、data[3]=3 で止まって j＝3。ここで i ≧ j（3 ≧ 3）が成立するため値の入替えをせずに繰返しを終了します。よって α を最初に実行する時点では data は未変更のままで、出力は「2 1 3 5 4」となり正解はエです。（出典: 令和5年度 基本情報技術者試験 科目B 問3）
一問一答
科目A 180問+科目B 60問