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

選択肢

• ア基数ソート
• イクイックソート
• ウ選択ソート
• エ挿入ソート

正解と解説

正解：イ クイックソート

分割統治法は、問題を小さな部分問題に分割し、それぞれを解いてから統合する考え方です。クイックソートは基準値（ピボット）で列を2つに分割し、各部分を再帰的に整列するため分割統治に該当します。マージソートも同じく分割統治型です。

選択肢ごとの解説

• ア桁ごとにバケットへ振り分けて安定的に並べる方式で、分割統治ではありません。
• イ正解。ピボットで2分割して再帰的に整列する典型的な分割統治法です。
• ウ最小値を探して先頭と交換する単純な繰り返しで、分割はしません。
• エ整列済み部分に1件ずつ挿入していく方式で、分割統治ではありません。

この問題に出た用語

• 整列アルゴリズムの計算量
• 分割統治法
• 整列アルゴリズム（バブルソート・選択ソート・挿入ソート）
• 整列（ソート）
• 選択ソート

同じ分野の他の問題

• fact(n)は，非負の整数nに対してnの階乗を返す。fact(n)の再帰的な定義はどれか。2025年度 春期 午前 問7
• 0≦x≦1の範囲で単調に増加する連続関数f(x)がf(0)<0≦f(1)を満たすときに，区間内でf(x)=0であるxの値…2025年度 春期 午前 問2
• 整列方法に関するアルゴリズムの記述のうち、バブルソートの記述はどれか。ここで、整列対象は重複のない1から9の数字がランダ…2024年度 春期 午前 問7
• 正の整数Mに対して、次の二つの流れ図に示すアルゴリズムを実行したとき、結果xの値が等しくなるようにしたい。aに入れる条件…2024年度 春期 午前 問5
• あるデータ列を整列したら状態0から順に状態1、2、・・・・、Nへと推移した。整列に使ったアルゴリズムはどれか。2023年度 秋期 午前 問6