応用情報技術者試験 応用情報技術者試験 令和5年度春期 午前 問7: 配列に格納されたデータ 2，3，5，4，1 に対して，クイックソートを用いて昇順に並べ替える。2 回目の分割が終わった状態はどれか。ここで，分割は基準値より小さ

問題本文

配列に格納されたデータ 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，2，3，5，4

解説

クイックソートは、基準値（ピボット）より小さいグループと大きいグループに分割する操作を繰り返すアルゴリズムです。1 回目は配列 2,3,5,4,1 の左端 2 を基準値とし、小さいグループ{1}と大きいグループ{3,5,4}に分けて「1, 2, 3,5,4」になります。2 回目は分割対象のグループの左端を基準値にしますが、左側の{1}は要素が 1 つで分割不要なので、大きいグループ{3,5,4}を分割します。その左端 3 を基準値にすると小さい側は空、大きい側は{5,4}となり、全体は「1, 2, 3, 5,4」のまま変わりません。よって 2 回目の分割が終わった状態は ア（1，2，3，5，4）です。

選択肢ごとの解説

• ア.1 回目で 2 を基準に「1,2,(3,5,4)」、2 回目で(3,5,4)を 3 を基準に分割（小さい側は空、大きい側は 5,4）した結果が「1,2,3,5,4」となり正しい。
• イ.末尾が 4,3 となっており、元のグループ内順序（5,4 の順）を保つという条件に反するため誤り。
• ウ.先頭の 2 がまだ確定位置に移っておらず 1 回目の分割すら反映されていないため誤り。
• エ.末尾に 1 が残っており、1 回目の分割（小さい 1 を 2 の前に置く）が行われていない並びなので誤り。