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

解説

正解は2です。 基準値（ピボット）を選んでデータを小さいグループと大きいグループに分け、それぞれに同じ操作を再帰的に繰り返すのは、クイックソートの手順です。 基準値によって前半と後半がほぼ同じ大きさに分かれるほど、効率が良くなります。 【選択肢別解説】 1：× 基数ソートは、数値を桁ごとに振り分ける操作を、下位の桁から順に繰り返す整列法です。 基準値による分割は行いません。 2：○ クイックソートは、基準値より小さいデータを前に、大きいデータを後に集め、分かれた並びに同じ操作を再帰的に適用します。 文章の内容と一致し、平均計算量はO(n log n)です。 3：× バブルソートは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返す整列法です。 分割や再帰は使いません。 4：× マージソートは、データを半分ずつに分割して整列し、整列済みの並びどうしを併合（マージ）する整列法です。 基準値の大小で振り分けるのではなく、併合の段階で並べ替えます。 【ポイント】 クイックソートは基準値の選び方が悪いと分割が偏り、最悪の計算量がO(n²)になります。 「基準値で分割」ならクイックソート、「分割して併合」ならマージソートと区別します。