平成23年度 特別 午前 問8

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

解説

基準を一つ決めて大小の2組に割り、繰り返します。

クイックソートの要は、比べる相手を一つに絞り込むところにあります。まず対象の集合から基準になる要素を一つ選び、それより大きいものの集まりと小さいものの集まりに振り分けます。この一度の振り分けで、小さい側と大きい側は二度と混ざりませんので、あとはそれぞれの集まりの中だけを考えればよくなります。同じ操作を各集まりに繰り返し当てていくと、集まりはどんどん小さくなり、最後に並びが定まります。判定の軸は、毎回すべてを見渡して一つずつ取り出すのか、それとも一度の操作で対象そのものを二つに割って問題を小さくするのかという違いです。

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

• イ対象集合から最も小さい要素を順次取り出し…：残っているものの中から最も小さいものを探して取り出す操作を繰り返す手順です。対象そのものを二つに割る操作がないので、取り出すたびに残り全体を見渡すことになります。
• ウ対象集合から要素を順次取り出し，それまで…：取り出した要素を、すでに並べ終えた側の正しい位置に差し込んでいく手順です。並べ終えた部分が少しずつ伸びていく形で、基準を決めて振り分ける操作は出てきません。
• エ隣り合う要素を比較し，逆順であれば交換し…：隣り合うものだけを見比べて、順序が逆になっていれば入れ替える手順です。比べる範囲が隣どうしに限られており、対象を大小の二組に分けるという考え方とは異なります。