応用情報技術者 2019年 秋期 午前2 問08
問題文
分割統治を利用した整列法はどれか。
選択肢
ア：基数ソート
イ：選択ソート（正解）
ウ：クイックソート
エ：挿入ソート
分割統治を利用した整列法【午前2 解説】
要点まとめ
- 結論：分割統治法を利用した整列法はウ: クイックソートです。
- 根拠：分割統治法は問題を小さな部分に分割し、それぞれを解決してから統合する手法で、クイックソートはこれを典型的に用いています。
- 差がつくポイント：基数ソートや選択ソート、挿入ソートは分割統治法を使わず、アルゴリズムの構造が異なるため区別が重要です。
正解の理由
クイックソートは配列を基準値（ピボット）で分割し、左右の部分配列を再帰的に整列する分割統治法の代表的なアルゴリズムです。
選択ソートや挿入ソートは単純な比較と交換を繰り返す手法で、分割して解く構造を持ちません。基数ソートは桁ごとに処理する非比較型の整列法です。
選択ソートや挿入ソートは単純な比較と交換を繰り返す手法で、分割して解く構造を持ちません。基数ソートは桁ごとに処理する非比較型の整列法です。
よくある誤解
選択ソートが「選ぶ」動作から分割統治に見えることがありますが、実際は単純な逐次探索と交換の繰り返しです。
基数ソートは分割統治とは無関係に桁ごとに処理を行うため混同しやすいです。
基数ソートは分割統治とは無関係に桁ごとに処理を行うため混同しやすいです。
解法ステップ
- 分割統治法の基本概念を理解する（問題を分割し、解決し、統合する）。
- 各整列法のアルゴリズム構造を確認する。
- クイックソートがピボットで分割し再帰的に整列することを把握する。
- 選択ソートや挿入ソートは単純な比較交換で分割統治法ではないと判断する。
- 基数ソートは非比較型で分割統治法とは異なることを確認する。
選択肢別の誤答解説
- ア: 基数ソート
桁ごとに処理する非比較型整列で、分割統治法は使いません。 - イ: 選択ソート
配列を分割して再帰的に処理するわけではなく、最小値を選んで交換する単純な手法です。 - ウ: クイックソート
ピボットで分割し、左右の部分配列を再帰的に整列する典型的な分割統治法です。 - エ: 挿入ソート
部分的に整列済みの配列に要素を挿入する手法で、分割統治法は使いません。
補足コラム
分割統治法は多くのアルゴリズム設計の基本で、整列以外にも探索や数値計算で活用されます。
マージソートも分割統治法を用いた整列法の代表例で、クイックソートと並んで重要です。
クイックソートは平均計算量がで高速ですが、最悪計算量はになる点に注意が必要です。
マージソートも分割統治法を用いた整列法の代表例で、クイックソートと並んで重要です。
クイックソートは平均計算量がで高速ですが、最悪計算量はになる点に注意が必要です。
FAQ
Q: クイックソートとマージソートの違いは何ですか？
A: クイックソートはピボットで分割し部分配列を再帰的に整列、マージソートは配列を半分に分割し整列後にマージします。
A: クイックソートはピボットで分割し部分配列を再帰的に整列、マージソートは配列を半分に分割し整列後にマージします。
Q: 基数ソートはなぜ分割統治法ではないのですか？
A: 基数ソートは桁ごとに処理を行う非比較型整列で、問題を分割して再帰的に解く構造を持ちません。
A: 基数ソートは桁ごとに処理を行う非比較型整列で、問題を分割して再帰的に解く構造を持ちません。
関連キーワード: 分割統治法、クイックソート、整列アルゴリズム、アルゴリズム設計、再帰、ピボット
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！