修了試験 2011-12-18実施分 基本情報技術者試験 問6

解説

正解は2です。 文章は、基準値より小さいデータを前半に、大きいデータを後半に分ける整列法を説明しています。 さらに、分けた前半と後半それぞれに同じ操作を再帰的に繰り返します。 これはクイックソートの手順です。 基準値（ピボット）は、分割後の前半と後半が同程度の大きさになるように選ぶと効率が良くなります。 【選択肢別解説】 1：× 基数ソートは、データを1の位、10の位と桁ごとに振り分けて並べ直す方法です。 基準値による分割や再帰は行いません。 2：○ 基準値を境に2つに分け、各部分を再帰的に同じ方法で整列するのはクイックソートです。 平均の計算量はn log nですが、分割が偏ると効率が落ちます。 3：× バブルソートは、隣り合うデータを比較し、順序が逆なら交換する操作を繰り返す方法です。 基準値による分割は使いません。 4：× マージソートも再帰的に分割しますが、分割は単に半分にするだけです。 整列済みの並びどうしを併合（マージ）する点が特徴で、基準値で大小を振り分けはしません。 【ポイント】 クイックソートは「基準値で大小に分割」、マージソートは「半分に分けて後で併合」と区別しましょう。 クイックソートは、基準値が最大値や最小値に偏ると、最悪でnの2乗の計算量になります。