平成21年度 秋期 午前 問6

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

解説

基準値で二分し各組で同じ操作を繰り返します。

整列の方法は、一回のひと手間で何をするかを見れば区別できます。見分ける軸はそこ一点です。既にそろった並びへ新しい要素を割り込ませていくやり方、未整列の部分から最も小さいものを取り出して前へ送るやり方、となりどうしを見比べて必要なら交換するやり方、そして基準となる値を一つ決めて列を二つの組に切り分け、切り分けた先でも同じことを繰り返すやり方があります。クイックソートは最後のものです。基準値より小さい側と大きい側に分け、分けた組の中でまた基準値を選んで分け続けるので、分けて片づけるという進め方になります。平均すると速い一方、基準値の選び方が偏ると分割がなかなか進まず、時間が延びる場面もあります。

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

• ア既に整列済みのデータ列の正しい位置に，デ…：整列済みのデータ列の正しい位置にデータを追加する操作を繰り返す方法です。列を組に割る手順を含まず、一つずつ差し込んで並びを伸ばしていきます。
• イデータ中の最小値を求め，次にそれを除いた…：データ中の最小値を求め、それを除いた部分でまた最小値を求める操作を繰り返す方法です。基準となる値で二つに割るのではなく、毎回いちばん小さいものを確定させます。
• エ隣り合ったデータの比較と入替えを繰り返す…：隣り合ったデータの比較と入替えを繰り返す方法です。比べる相手が常に隣に限られるため、列全体を二つの組に分けるという手順は出てきません。