高度情報処理技術者試験・情報処理安全確保支援士試験 令和5年度 春期 午前I 問3
配列に格納されたデータ2、3、5、4、1に対して、クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで、分割は基準値より小さい値と大きい値のグループに分けるものとする。また、分割のたびに基準値はグループ内の配列の左端の値とし、グループ内の配列の値の順番は元の配列と同じとする。
選択肢を押すと答え合わせができます。
正解と解説を見る
【正解】ア
最初の配列は「2、3、5、4、1」です。1回目の分割では、左端の2を基準値とします。2より小さい値は1だけで、2より大きい値は3、5、4です。各グループ内では元の順番を保つので、「1｜2｜3、5、4」となり、配列全体は「1、2、3、5、4」になります。
次に、要素が一つだけの「1」はそれ以上分割する必要がないため、未整列のグループ「3、5、4」を分割します。2回目の基準値は、このグループの左端にある3です。3より小さい値はなく、3より大きい値は元の順番のまま5、4となります。したがって、分割後も「3、5、4」の並びは変化せず、配列全体は「1、2、3、5、4」です。
イの「1、2、5、4、3」は誤りです。2回目の基準値3より大きい5と4は、基準値の右側に置かれる必要があります。3を末尾に移す並びにはなりません。
ウの「2、3、1、4、5」は誤りです。1回目の基準値2より小さい1が、2の右側に残っているので、最初の分割条件を満たしていません。
エの「2、3、4、5、1」も誤りです。基準値2より小さい1が末尾にあり、1回目の分割が正しく反映されていません。
【ポイント】 クイックソートでは、基準値を境に小さい値のグループと大きい値のグループを作り、それぞれを再帰的に分割します。 本問では、グループ内の相対的な順番を維持するという条件を必ず反映させます。
出典：令和5年度 春期 高度情報処理技術者試験・情報処理安全確保支援士試験 午前I 問3
※ 解説は SkillStack 編集部が作成したものです。Web 表示のため、図表の配置や表記を一部改めています。
この回の30問を、アプリで通しで解く
- 本番と同じ問題数・制限時間で通し演習（模試モード）
- 間違えた問題は自動で「復習すべき問題」に回る
- 解説で分からない点はAIに質問できる