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

正解 イ

分割統治を使う整列法はクイックソートです。基準値で列を2つに分け、それぞれを再帰的に整列します。

分割統治は、大きな問題を小さな部分問題に分けて解き、その結果をまとめる手法です。クイックソートは、基準値（ピボット）より小さい要素と大きい要素に列を分けます。分けた部分列に同じ処理を再帰的に繰り返して整列します。平均の計算量はO(n log n)です。分割統治を使う整列法には、ほかにマージソートがあります。

ア：基数ソートは、キーの桁ごとに下位桁から順に振り分けを繰り返す整列法です。列を分割して再帰的に解くものではありません。

ウ：選択ソートは、未整列部分から最小（最大）の要素を選び、先頭と交換することを繰り返す整列法です。

エ：挿入ソートは、未整列部分の要素を1つずつ取り出し、整列済み部分の適切な位置に挿入する整列法です。

出典：令和元年度 秋期 応用情報技術者試験 問8