応用情報技術者試験 令和元年秋 午前問8 解説付き過去問
問題
分割統治を利用した整列法はどれか。
正解
解説
この問題は、代表的な整列(ソート)アルゴリズムの中から、「分割統治法(Divide and Conquer)」の考え方を利用しているものを選ぶ問題です。
- 分割統治法の概要
分割統治法とは、問題を解く際に以下の3つのステップで処理を進める手法です。
- 問題を複数の小さな部分に分割する(Divide)
- 分割された問題を個別に解く(Conquer)
- 得られた部分的な解を統合して最終的な解とする(Combine)
- 問題を複数の小さな部分に分割する(Divide)
- クイックソートの特徴
クイックソートは分割統治法を典型的に用いたソートアルゴリズムです。
基準(ピボット)となる要素を1つ選び、それより小さい値と大きい値の2つの部分に分割(Divide)し、それぞれの部分について再帰的にクイックソートを適用(Conquer)し、最終的に並べ替えた結果を得ます(Combine)。
このようにしてソートを進めることで、効率的な並び替えを実現します。平均計算量はO(n log n)です。 - 他の選択肢との比較
・基数ソートは桁ごとに分類して整列する手法で、分割統治法とは異なります。
・選択ソートや挿入ソートは、配列を順番に走査しながら整列していくため、分割統治を用いた手法ではありません。
したがって、分割統治を利用した整列法として正しいのは、クイックソートです。