令和5年度 春期 ITストラテジスト試験 システムアーキテクト試験 ネットワークスペシャリスト試験 ITサービスマネージャ試験 情報処理安全確保支援士試験 午前Ⅰ 問題【共通】 問3

クイックソートにおける分割処理の過程を順を追って確認します。

クイックソートは、配列から基準値を選び、それより「小さいグループ」と「大きいグループ」に分割する操作を再帰的に繰り返すアルゴリズムです。本問では「基準値はグループ内の左端の値」「グループ内の値の順番は元の配列と同じ」というルールに従います。

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 が右端に残っており、基準値に対する大小の振り分けが正しく行われていません。