応用情報技術者試験 令和5年春 午前問7 解説付き過去問
問題
配列に格納されたデータ2、3、5、4、1に対して、クイックソートを用いて昇順に並べ替える。
2回目の分割が終わった状態はどれか。
ここで、分割は基準値より小さい値と大きい値のグループに分けるものとする。
また、分割のたびに基準値はグループ内の配列の左端の値とし、グループ内の配列の値の順番は元の配列と同じとする。
正解
解説
この問題は、クイックソートにおいて2回目の分割後の状態がどうなるかを問うものです。以下の手順で、実際に操作を確認していきます。
- 初期配列
最初に与えられた配列は以下のとおりです。
[2, 3, 5, 4, 1] - 1回目の分割
配列全体に対して分割を行います。
基準値は配列の左端、すなわち「2」です。
これにより、基準値「2」より小さい要素 → [1]、2より大きい要素 → [3, 5, 4] に分けます。
このとき、要素の順番は元の配列に従うため、基準値と各グループを元の順で並べると、次のようになります。 - 2回目の分割
再帰的に分割を行います。次に分割されるのは、基準値の右側にある [3, 5, 4] です。
このグループの基準値は左端の「3」です。
3より小さい要素 → なし、3より大きい要素 → [5, 4] となります。
順番を維持して並べると [3, 5, 4] はそのままです。 - 2回目の分割後の全体
分割された部分を含めて全体を表すと、次のようになります。
[1, 2, 3, 5, 4]
[1, 2, 3, 5, 4]
したがって、クイックソートにおける2回目の分割が終わった状態は [1, 2, 3, 5, 4] です。