情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和5年度春期 午前Ⅰ 問3: 配列に格納されたデータ 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で{1}と{3,5,4}に分かれ1,2,3,5,4となる。2回目は右側{3,5,4}を基準3で分割するが3より小さい値はなく{5,4}が残るため並びは1,2,3,5,4のまま。よってアが正解。実務では分割統治の動作を一手ずつ追える理解が、計算量や最悪ケース把握の前提になる。

選択肢ごとの解説

• ア.1回目で2を基準に1と3,5,4へ分割、2回目で3を基準に分割した結果がこの並びで正しい。
• イ.末尾の3と5,4の順が崩れており、基準3による分割後の正しい配置になっていない。
• ウ.1回目の基準2による分割すら反映されておらず、1が前へ来ていない誤った状態。
• エ.1が末尾に残ったままで、最初の分割で小さい値1が前に来る動作と矛盾する。