令和5年度春期 情報処理安全確保支援士 午前Ⅰ 問3

午前I 問03：左端を基準にして、順番を崩さずグループ分けしよう

まず左端の 2 を基準にすると、2 より小さい `1` と、2 より大きい `3,5,4` に分かれるよ。このとき、元の並び順はそのまま保つのがポイント。次に右側の `3,5,4` でも左端の 3 を基準に分けると、全体は `2,3,1,4,5` の形として追えるよ。

この問題で問われていること

この問題のカギは、ただ分割することではなく、「左端を基準にする」「元の順序を保つ」という指定どおりに、並びの変化を落ち着いて追えるかどうかだよ。

Quick Sort Partition Trace

pivot=2 then pivot=3 with original relative order preserved in each group

2,3,5,4,1\n-> 1 | 2 | 3,5,4\n-> 2,3,1,4,5 (state after 2nd partition)

確認ポイント

• 各グループ内では元の並びを保つ。
• 毎回左端が基準値です。
• 2 回目の分割直後の状態を問うている。

正解

ア

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア（正解）

これは正解だよ。クイックソートでは、まず左端の2を基準にして、2より小さい1を左、2より大きい3,5,4を右に分けるんだ。次に右側のグループは左端の3を基準にして、3と5,4に分かれる。荷物を『基準より小さい箱・基準・大きい箱』に順番に仕分ける感じで、2回目の分割後は 1,2,3,5,4 になるよ。

選択肢イ

これは不正解だよ。1,2 までは合っているけど、3を基準にした2回目の分割では、3は5,4より前に置かれる必要があるんだ。受付で『3番の人を窓口にして、その後ろに5番と4番が並ぶ』イメージだから、1,2,5,4,3 のように3が最後へ回るのはおかしいよ。

選択肢ウ

これは不正解だよ。左端の2を基準にした最初の分割で、2より小さい1は左側へ移動するはずだよ。2,3,4,5,1 のように1が最後にいるのは、仕分け箱に入れるべき荷物を入れ忘れたようなもの。2回目どころか1回目の分割後の形としても合っていないよ。

選択肢エ

これは不正解だよ。1回目の分割だけでも、左端の2を基準にすると、2より小さい1は2の左側に来ないといけないんだ。なのに 2,3,1,4,5 では1が後ろに残っている。泥棒チェックで『2より小さい人はこちら』と言われた1番さんが、まだ列の奥にいるような状態だから違うよ。