| ソフトウェア開発技術者試験 |
2006年度 ＝ 平成18年度・春期 |
午前 |
問12 |
分割統治を適用した整列（ソート）アルゴリズムはどれか。
| ア 基数ソート
| イ クイックソート
|
| ウ 選択ソート
| エ 挿入ソート
|
イ
分割統治法は、問題を幾つかの互いに重ならない部分問題に分け、それぞれの解を得ることによって全体の解を求めようとする問題解決の方法です。
分割統治法を用いる代表的なソートアルゴリズムは、クイックソートとマージソートです。
クイックソート（quick sort）は、C.A.R.Hoareが開発した、高速なソートアルゴリズムです。
データを適当な基準値（通常ピボットと呼ばれます）より小さなグループと大きなグループに分割し、それぞれのグループで新しい基準値を選び、同様に分割を繰り返すことによってソートを行います。
