平成30年度 秋期 午前 問6

✓ これが正解ウ適当な基準値を選び，それよりも小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。

解説

基準値で二つに分け、同じ手順を繰り返していく方法です。

クイックソートは、並べ替えたい範囲から基準となる値を一つ選ぶところから始まります。その値より小さいものの集まりと、大きいものの集まりに分けます。分けた時点で、基準値の置かれる位置は最終的な場所として確定します。次に、できた二つの集まりのそれぞれで同じ手順を繰り返します。範囲が一つの要素になるまで分割を続けると、全体が整った並びになります。分けるたびに扱う範囲が半分ほどに減るので、要素数が多いときの速さにつながります。ただし基準値の選び方が偏ると分割も偏り、期待した速さが出ないことがあります。あらかじめ整っている並びに対して端の値を基準に選ぶと、この偏りが起こりやすくなります。中央に近い値を選び直す工夫が使われます。同じ手順を小さくなった範囲へ当て直す点が、整列の中でも特徴的です。

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

• ア既に整列済みのデータ列の正しい位置に，デ…：整った並びの正しい位置へ値を差し込む操作を繰り返す方法で、挿入ソートの説明です。手前から順に整った領域を広げていく形で、範囲を分割する動きはありません。ほぼ整った並びに対しては速く働くという性質を持ちます。比較の回数も少なくなります。
• イデータ中の最小値を求め，次にそれを除いた…：残りの中から最小値を探して取り出す操作を繰り返す方法で、選択ソートの説明です。毎回すべてを見比べるため、要素数が増えると比較の回数が急に増えていきます。基準値を選んで振り分けるという考え方は使われていません。
• エ隣り合ったデータの比較と入替えを繰り返す…：隣り合う二つを比べて入れ替える操作を繰り返す方法で、バブルソートの説明です。値が少しずつ端へ移っていく動きが特徴で、交換の回数が多くなりがちです。部分ごとに切り分けて処理していく構造にはなっていません。