応用情報技術者試験ナビ ロゴ 応用情報技術者試験ナビ
合格発表日:2025年7月3日(あと12日)

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

問題

分割統治を利用した整列法はどれか。

正解

解説

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

  1. 分割統治法の概要
    分割統治法とは、問題を解く際に以下の3つのステップで処理を進める手法です。
    1. 問題を複数の小さな部分に分割する(Divide)

    2. 分割された問題を個別に解く(Conquer)

    3. 得られた部分的な解を統合して最終的な解とする(Combine)

    この手法は、計算量を抑えながら効率的に問題を解くことができるため、特にソートアルゴリズムでよく用いられます。

  2. クイックソートの特徴
    クイックソートは分割統治法を典型的に用いたソートアルゴリズムです。
    基準(ピボット)となる要素を1つ選び、それより小さい値と大きい値の2つの部分に分割(Divide)し、それぞれの部分について再帰的にクイックソートを適用(Conquer)し、最終的に並べ替えた結果を得ます(Combine)。

    このようにしてソートを進めることで、効率的な並び替えを実現します。平均計算量はO(n log n)です。

  3. 他の選択肢との比較
    ・基数ソートは桁ごとに分類して整列する手法で、分割統治法とは異なります。
    ・選択ソートや挿入ソートは、配列を順番に走査しながら整列していくため、分割統治を用いた手法ではありません。

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