応用情報技術者 2023年 春期 午前2 問07
問題文
配列に格納されたデータ2, 3, 5, 4, 1に対して、クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで、分割は基準値より小さい値と大きい値のグループに分けるものとする。また、分割のたびに基準値はグループ内の配列の左端の値とし、グループ内の配列の値の順番は元の配列と同じとする。
選択肢
ア：1, 2, 3, 5, 4（正解）
イ：1, 2, 5, 4, 3
ウ：2, 3, 1, 4, 5
エ：2, 3, 4, 5, 1
クイックソートの分割2回目の状態【午前2 解説】
要点まとめ
- 結論：2回目の分割終了時の配列は1, 2, 3, 5, 4となる。
- 根拠：基準値は各分割で左端の値を選び、元の順序を保ちながら小さい値と大きい値に分けるため。
- 差がつくポイント：基準値の選び方と分割後の配列の順序保持を正確に理解しているかが鍵。
正解の理由
クイックソートの1回目の分割では、左端の値「2」を基準に配列を小さい値と大きい値に分けます。
元の順序を保つため、2より小さい値は「1」、大きい値は「3, 5, 4」となり、分割後は「1, 2, 3, 5, 4」。
2回目の分割は左側の「1」のみのグループと右側「3, 5, 4」のグループに分け、左側は1要素なので右側「3, 5, 4」を基準値「3」で分割。
3より小さい値はなく、3は左端なのでそのまま、右側は「5, 4」。
分割後は「1, 2, 3, 5, 4」となり、これが2回目の分割終了時の状態です。
元の順序を保つため、2より小さい値は「1」、大きい値は「3, 5, 4」となり、分割後は「1, 2, 3, 5, 4」。
2回目の分割は左側の「1」のみのグループと右側「3, 5, 4」のグループに分け、左側は1要素なので右側「3, 5, 4」を基準値「3」で分割。
3より小さい値はなく、3は左端なのでそのまま、右側は「5, 4」。
分割後は「1, 2, 3, 5, 4」となり、これが2回目の分割終了時の状態です。
よくある誤解
基準値を毎回配列の左端から選ぶことを忘れ、ランダムや中央の値を選ぶ誤解。
分割後の配列の順序が変わると考え、元の順序を保持しない誤解。
分割後の配列の順序が変わると考え、元の順序を保持しない誤解。
解法ステップ
- 初期配列は「2, 3, 5, 4, 1」。
- 1回目の分割：基準値は左端の「2」。
- 「2」より小さい値は「1」、大きい値は「3, 5, 4」。
- 分割後の配列は「1, 2, 3, 5, 4」。
- 2回目の分割は左側「1」と右側「3, 5, 4」に分ける。
- 左側は1要素なので分割不要。右側の基準値は「3」。
- 「3」より小さい値はなく、「3」は左端のまま。
- 分割後の配列は変わらず「1, 2, 3, 5, 4」。
選択肢別の誤答解説
- イ: 「1, 2, 5, 4, 3」→「3」と「5,4」の順序が変わっており、元の順序保持のルールに反する。
- ウ: 「2, 3, 1, 4, 5」→1回目の分割で「1」が左端に来ていないため誤り。
- エ: 「2, 3, 4, 5, 1」→「1」が最後に残っているが、1回目の分割で「1」は左側に移動すべき。
補足コラム
クイックソートは分割（パーティショニング）で基準値を選び、配列を小さい値と大きい値に分ける手法です。
基準値の選び方や分割後の配列の順序保持ルールは実装によって異なりますが、問題文の条件を正確に理解することが重要です。
基準値の選び方や分割後の配列の順序保持ルールは実装によって異なりますが、問題文の条件を正確に理解することが重要です。
FAQ
Q: クイックソートの基準値は必ず左端ですか？
A: 問題文の条件によりますが、一般的には任意の位置を基準値にできます。今回は左端指定です。
A: 問題文の条件によりますが、一般的には任意の位置を基準値にできます。今回は左端指定です。
Q: 分割後の配列の順序は変わっても良いのですか？
A: 今回の問題では元の順序を保持する条件があるため、順序を変えてはいけません。
A: 今回の問題では元の順序を保持する条件があるため、順序を変えてはいけません。
関連キーワード: クイックソート、分割、パーティショニング、昇順ソート、配列操作
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！