応用情報技術者試験 令和元年秋 午前問8 解説付き過去問

この問題は、代表的な整列（ソート）アルゴリズムの中から、「分割統治法（Divide and Conquer）」の考え方を利用しているものを選ぶ問題です。

1. 分割統治法の概要
   分割統治法とは、問題を解く際に以下の3つのステップで処理を進める手法です。
   
   1. 問題を複数の小さな部分に分割する（Divide）
      
      
   2. 分割された問題を個別に解く（Conquer）
      
      
   3. 得られた部分的な解を統合して最終的な解とする（Combine）
      
      
   この手法は、計算量を抑えながら効率的に問題を解くことができるため、特にソートアルゴリズムでよく用いられます。
   
   
2. クイックソートの特徴
   クイックソートは分割統治法を典型的に用いたソートアルゴリズムです。
   基準（ピボット）となる要素を1つ選び、それより小さい値と大きい値の2つの部分に分割（Divide）し、それぞれの部分について再帰的にクイックソートを適用（Conquer）し、最終的に並べ替えた結果を得ます（Combine）。
   
   このようにしてソートを進めることで、効率的な並び替えを実現します。平均計算量はO(n log n)です。
   
   
3. 他の選択肢との比較
   ・基数ソートは桁ごとに分類して整列する手法で、分割統治法とは異なります。
   ・選択ソートや挿入ソートは、配列を順番に走査しながら整列していくため、分割統治を用いた手法ではありません。
   
   

したがって、分割統治を利用した整列法として正しいのは、クイックソートです。