令和5年度 春期 応用情報技術者試験 問7

解説

正解は1です。 基準値を左端の値とし、基準値より小さいグループと大きいグループに分ける操作を順にたどります。 グループ内の値は元の配列の順番を保ちます。 【手順】 初めの配列は2，3，5，4，1です。 1回目の分割では基準値は左端の2です。 2より小さい値は1だけで、大きい値は元の順番のまま3，5，4です。 1回目の分割後は1，2，3，5，4となります。 左のグループ{1}は要素が一つなので、これ以上分割しません。 2回目の分割は右のグループ3，5，4が対象で、基準値は左端の3です。 3より小さい値はなく、大きい値は元の順番のまま5，4です。 2回目の分割後も配列は1，2，3，5，4です。 【選択肢別解説】 1：○ 上の手順のとおり、2回目の分割が終わった状態は1，2，3，5，4です。 2：× 1，2，5，4，3は、2回目の分割で3を末尾に移した形です。 3は基準値なので、大きいグループ5，4の前に置かれます。 3：× 2，3，1，4，5は、1回目の基準値2による分割が行われていない並びです。 2より小さい1が2の後ろに残っています。 4：× 2，3，4，5，1も、基準値2より小さい1が末尾に残っており、分割の結果になっていません。 【ポイント】 クイックソートは、基準値（ピボット）を境に小さいグループと大きいグループへ分ける操作を、グループごとに繰り返す整列法です。 平均の計算量はn log nですが、すでに整列済みのデータではn²に近くなります。