令和5年度 春期 応用情報技術者試験 午前 問7

クイックソートの分割手順

クイックソートは、基準値（ピボット）を選び、それより小さい値のグループと大きい値のグループに分割する操作を再帰的に繰り返す整列アルゴリズムです。

本問のルール：

• 基準値はグループ内の配列の左端の値
• 分割後の値の順番は、元の配列と同じ順序を保つ

【初期状態】
$2, 3, 5, 4, 1$

【1回目の分割】
対象：$2, 3, 5, 4, 1$

1. 基準値は左端の $2$。
2. $2$ より小さい値のグループ：$1$
3. $2$ より大きい値のグループ：$3, 5, 4$ （元の順番を維持）
   結果、これらを「小さい値」「基準値」「大きい値」の順に並べます。
   1回目の分割後の状態：$1, 2, 3, 5, 4$
   この時点で、$1$ と $3, 5, 4$ の2つのグループに分かれます。

【2回目の分割】
左側のグループ $1$ は要素数が1つのため、これ以上分割できません（整列済み）。
したがって、右側のグループ $3, 5, 4$ に対して2回目の分割を行います。
対象：$3, 5, 4$

1. 基準値は左端の $3$。
2. $3$ より小さい値のグループ：なし
3. $3$ より大きい値のグループ：$5, 4$ （元の順番を維持）
   結果、並べ替えても $3, 5, 4$ のままです。
   全体の配列として見ると、状態は $1, 2, 3, 5, 4$ となります。

よって、2回目の分割が終わった状態は「ア」です。

各選択肢の解説

• ア: 正解。上記の手順通り、2回目の分割が終了した時点での正しい配列です。
• イ: $1, 2, 5, 4, 3$。2回目の分割で基準値を誤って処理した場合などの結果です。
• ウ: $2, 3, 1, 4, 5$。分割のルールや対象グループを誤って処理した結果です。
• エ: $2, 3, 4, 5, 1$。他の整列アルゴリズム（バブルソートなど）の途中経過と混同している可能性があります。