令和5年度 春期 午前 問7

✓ これが正解ア1，2，3，5，4

解説

二回目の分割でも並びは動きません。

設問は、2，3，5，4，1という並びをクイックソートで昇順にするとき、2回目の分割が終わった状態を四つから選ばせています。見分けの軸は、基準値を毎回どこから取るかと、どのグループから順に分割していくか、という二点です。設問は基準値をそのグループの左端とし、グループ内の値の順番は元のままだと断っています。1回目は全体の左端である2を基準にし、小さい側に1が、大きい側に3，5，4が入るので、並びは1，2，3，5，4になります。2回目は左のグループから進みますが、そこは要素が一つしかなく既に確定しているため、次に割るのは右の3，5，4で、基準値はその左端の3です。3より小さい値がこのグループには無いので、大きい側に5，4がそのまま残り、並びは一つも動きません。よって2回目を終えた状態は1回目と同じ形になります。分割が何も動かさないことはあり得る、というのがこの問の要点です。

ほかの選択肢はなぜ違うのか

• イ1，2，5，4，3：1，2，5，4，3 という並びです。右側のグループの中で値の順番を入れ替えてしまった形にあたり、グループ内の値の順番は元の配列と同じという設問の断り書きに反しています。
• ウ2，3，1，4，5：2，3，1，4，5 という並びです。左端ではない値を基準に取ったときにできる形です。先頭の2が動いていないことからも、最初の分割で置いた基準が違っていると読み取れます。
• エ2，3，4，5，1：2，3，4，5，1 という並びです。末尾の1がそのまま残っているので、最初の基準値より小さい値がまだ前へ移されておらず、分割を終えた状態としては成り立ちません。