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

解説

正解は2。分割統治法は、大きな問題を小さな部分問題に分け、それぞれを解いてから結果をまとめる考え方。クイックソートは基準値（ピボット）を選んで列を「基準値より小さい群」と「大きい群」に分け、各群に同じ手順を再帰的に当てはめるので、分割統治を利用した整列法になる。平均の計算量はO(n log n)。

• 1の基数ソートは、キーの桁ごとに振り分けて並べ直す方法で、列を分けて再帰的に解く手法ではない。
• 3の選択ソートは、未整列部分から最小値を探して先頭と交換することを繰り返す。
• 4の挿入ソートは、整列済みの部分に次の要素を適切な位置へ差し込むことを繰り返す。

根拠：整列アルゴリズムの基本的な手法の分類。