FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次のクイックソートの分割処理を1回実行したとき、pivotの…
問題
次のクイックソートの分割処理を1回実行したとき、pivotの最終位置はどれか。配列の要素番号は1から始まる。
整数型の配列: a ← {6, 2, 7, 3, 5}
整数型: pivot ← a[5], i ← 0, j, tmp
for (j を 1 から 4 まで 1ずつ増やす)
if (a[j] ≦ pivot)
i ← i ＋ 1
tmp ← a[i]; a[i] ← a[j]; a[j] ← tmp
endif
endfor
tmp ← a[i + 1]; a[i + 1] ← a[5]; a[5] ← tmp
return i + 1- ア 2
- イ 3（正解）
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：3
pivotは末尾の5です。jを1から4まで見て、a[j]が5以下ならiを進めてa[i]とa[j]を交換します。2と3だけがpivot以下なので、それらが左側へ移ります。
| j | i | 配列 |
|---|---|---|
| 1 | 0 | {6,2,7,3,5} |
| 2 | 1 | {2,6,7,3,5} |
| 3 | 1 | {2,6,7,3,5} |
| 4 | 2 | {2,3,7,6,5} |
| pivot交換 | 3 | {2,3,5,6,7} |
pivotは3番目に置かれます。pivot値そのものではなく、最終位置i+1を返す点を読み取ってください。
選択肢の見分け方：2はpivot以下の個数だけを読んだ値、4や5はpivot交換前後の位置を取り違えた値です。最後にpivotをa[i+1]へ置く処理まで含めましょう。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。