令和5年度 春期 ITストラテジスト試験 システムアーキテクト試験 ネットワークスペシャリスト試験 ITサービスマネージャ試験 情報処理安全確保支援士試験 午前Ⅰ 問題【共通】 問3
テクノロジアルゴリズム
この問題は2023(R5)春 高度試験共通 午前Iに出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。
本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。
配列に格納されたデータ 2, 3, 5, 4, 1 に対して，クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで，分割は基準値より小さい値と大きい値のグループに分けるものとする。また，分割のたびに基準値はグループ内の配列の左端の値とし，グループ内の配列の値の順番は元の配列と同じとする。
解答・解説を読む
正解: 選択肢ア
クイックソートにおける分割処理の過程を順を追って確認します。
クイックソートは、配列から基準値を選び、それより「小さいグループ」と「大きいグループ」に分割する操作を再帰的に繰り返すアルゴリズムです。本問では「基準値はグループ内の左端の値」「グループ内の値の順番は元の配列と同じ」というルールに従います。
1回目の分割
- 初期状態: 2, 3, 5, 4, 1
- 基準値: 左端の
2 - 小さいグループ:
1 - 大きいグループ:
3, 5, 4(元の順番のまま) - 1回目の分割後の状態: 1, 2, 3, 5, 4
2回目の分割
次に、要素数が2以上のグループである 3, 5, 4 に対して分割を行います（左側の 1 は要素数が1つなので分割終了です）。
- 対象グループ: 3, 5, 4
- 基準値: 左端の
3 - 小さいグループ: なし
- 大きいグループ:
5, 4(元の順番のまま) - 2回目の分割後の状態: 1, 2, 3, 5, 4
2回目の分割が終わった時点でも配列の並びは 1, 2, 3, 5, 4 のままとなります。
各選択肢の解説
- ア: 2回目の分割終了時の状態と一致するため、正解です。
- イ: 要素の順番がルール（元の配列と同じ順番を保つ）に反しています。
- ウ: 1回目の分割が正しく行われておらず、基準値による大小の振り分けが不適切です。
- エ: 1回目の分割で
1が右端に残っており、基準値に対する大小の振り分けが正しく行われていません。