平成27年度 秋期 午前 問7

✓ これが正解ア対象集合から基準となる要素を選び，これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことによって，整列を行う。

解説

基準の要素で大小2組に分け、それを繰り返す方法です。

整列のやり方は、対象の集合をどう扱うかで見分けられます。クイックソートは、まず基準になる要素を1つ決め、それより大きいものの集まりと小さいものの集まりに二分します。分けた先でもまた基準を決めて同じことを行い、集まりが十分に小さくなるまで続けます。全体を割って小さくしていく点が、この方法の骨格です。見る軸は2つです。1つ目は、集合を分けてから中を整えるのか、それとも要素を1つずつ取り出して並べていくのか。2つ目は、比べる相手が集合全体に対する基準なのか、隣り合う要素どうしなのかです。この2点に当てはめれば、記述がどの手順を述べているかは絞り込めます。

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

• イ対象集合から最も小さい要素を順次取り出し…：毎回いちばん小さいものを選び出して前から並べていく手順で、対象を2つの集まりに割る場面がありません。分割ではなく選び出しを積み重ねる考え方です。
• ウ対象集合から要素を順次取り出し，それまで…：すでに整った並びの中の適切な位置へ差し込んでいく手順です。基準となる要素を決めて集まりを割る操作は現れず、並びを1つずつ育てていきます。
• エ隣り合う要素を比較し，逆順であれば交換し…：比べる相手が隣どうしに限られており、集合全体を見渡す基準が置かれていません。入れ替えを重ねて少しずつ順序を整えていく、別の手順の説明です。