令和元年度 秋期 応用情報技術者試験 午前 問8

解説

分割統治法は，問題を小さな部分問題に分割し，それぞれを同じ方法で解いてから結果を統合する手法です。クイックソートは基準値（ピボット）を境にデータを二つの部分列に分割し，各部分列に同じ手順を再帰的に適用するため，分割統治を利用した整列法に当たります（マージソートも同様です）。

選択肢ごとの解説

• ア誤り。基数ソートはキーを桁ごとにバケットへ分配して収集する処理を繰り返す分配法で，分割統治ではありません。
• イ正しい。クイックソートはピボットで二つの部分列に分割し，各部分列を再帰的に整列する分割統治法です。
• ウ誤り。選択ソートは未整列部分から最小値（最大値）を選んで先頭と交換する処理を繰り返す手法です。
• エ誤り。挿入ソートは整列済み部分に要素を 1 個ずつ正しい位置へ挿入していく手法です。