アルゴリズム (全97問中82問目)
No.82
分割統治法を適用した整列(ソート)アルゴリズムはどれか。
出典：平成18年春期 問12
- クイックソート
- 選択ソート
- 挿入ソート
- ヒープソート
- [出題歴]
- 応用情報技術者 R1秋期 問8
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
分割統治法は、大きな問題を同じ構造をもつ複数の小さな問題に分割し、その小さな問題の解を統合することで最終的に元の大きな問題を解決しようとする考え方です。
クイックソートは、整列対象のデータ群をある基準値以下のグループと基準値以上のグループに分割し、さらに分割後の各グループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムです。下図のように全体を小集団に分けながら整列を行うので、分割統治型の整列法と言えます。
なお、データ整列方法は「逐次添加法」「分割統治法」「データ構造の利用」などの種類に分類されます。
クイックソートは、整列対象のデータ群をある基準値以下のグループと基準値以上のグループに分割し、さらに分割後の各グループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムです。下図のように全体を小集団に分けながら整列を行うので、分割統治型の整列法と言えます。
- 逐次添加法
- バブルソート，基本選択法，基本挿入法，シェルソート
- 分割統治法
- クイックソート，マージソート
- データ構造の利用
- ヒープソート，2分探索木