令和元年度 秋期 午前 問8

✓ これが正解イクイックソート

解説

列を二つに割って同じ手順を繰り返すのがクイックソートです。

分割統治は、問題を小さな同じ形の問題へ割り、それぞれを解いてから結果を合わせる考え方です。クイックソートは基準となる値を一つ選び、それより小さい値の並びと大きい値の並びへ振り分けます。できた二つの並びに対して、まったく同じ手順をもう一度当てはめます。分けきった時点で全体は整っているため、後から合わせる作業は残りません。平均では要素数の対数に比例する深さまで分かれ、全体で n log n に比例する手間に収まります。基準の選び方が偏ると分割も片寄り、要素数の二乗に近い手間まで悪化します。そこで中央付近の値を選ぶ工夫が置かれます。分けた後の並びが片方へ寄らないほど深さは浅くなり、全体としても速く終わります。基準の選び方が効きます。マージソートも同じ考え方ですが、合わせる側に手間を置く点が違います。

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

• ア基数ソート：基数ソートは下の桁から順に値を見て、桁ごとに用意した入れ物へ配り直す手順を重ねます。並びを二つに割ってから同じ処理を呼び直す形ではなく、桁数の分だけ配り直しを繰り返す形です。配り直しの回数は桁数で決まります。
• ウ選択ソート：選択ソートは、まだ整っていない部分から最小の値を探して先頭へ移す作業を繰り返します。毎回すべてを見比べるので、分けて解くという発想がありません。手間は要素数の二乗に比例して増えていきます。分割の深さという考え方が現れません。
• エ挿入ソート：挿入ソートは、すでに整った並びへ次の要素を正しい位置に差し込んでいきます。全体を割らずに一つずつ取り込むので、分割統治には当たりません。ほとんど整っている並びに対しては短い時間で終わる長所があります。