クイックソートの分割
出典: 令和5年度 春期 応用情報技術者試験 午前 問7 (IPA)
配列に格納されたデータ 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
正解と解説を見る
正解: ア
- ア: 1 回目で 1, 2, 3, 5, 4 になり、2 回目 (基準値 3) でも並びが変わらないので正しい答えです。
- イ: 3 が 5, 4 の後ろに移っています。元の配列の順番を保つという条件に合いません。
- ウ: 2 より小さい 1 が、2 の後ろに残っています。
- エ: 2 より小さい 1 が、最後に残っています。
ポイント
- 1 回目: 基準値は左端の 2。小さい値 {1}、基準値 2、大きい値 {3, 5, 4} に分けて 1, 2, 3, 5, 4 になります。
- 2 回目: 大きい値のグループ {3, 5, 4} の基準値は左端の 3。3 より小さい値は無く、大きい値は {5, 4} なので、並びは変わらず 1, 2, 3, 5, 4 です。