平成18年春期試験午前問題 問12

分割統治法を適用した整列(ソート)アルゴリズムはどれか。

  • クイックソート
  • 選択ソート
  • 挿入ソート
  • ヒープソート
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
分割統治法は、大きな問題をいくつかの小さな問題に分割し、その小さな問題の解を統合することで最終的に問題を解決しようとする考え方です。

クイックソートは、n個のデータをある基準値以下の値のグループと基準値以上の値のグループに分割し、さらにそれぞれのグループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムです。下図のように全体を小集団に分けながら整列を行うので、分割統治型の整列法と言えます。
12.gif
なお、データ整列方法は「逐次添加法」「分割統治法」「データ構造の利用」などの種類に分類されます。
逐次添加法
バブルソート,基本選択法,基本挿入法,シェルソート
分割統治法
クイックソート,マージソート
データ構造の利用
ヒープソート,2分探索木

この問題の出題歴


Pagetop