問8
分割統治を利用した整列法はどれか。
ア 基数ソート
イ クイックソート
ウ 挿入ソート
エ 選択ソート
正解
イ
解説
整列法 (ソート) は、データを大きい順もしくは小さい順に並べ替える方法である。
また、分割統治は、大きな問題を小さな問題に分割して解くことで最終的に大きな問題を解く方法である。
ア 基数ソートは、下の桁から順に、桁ごとに小さい順に並べ替える方法である。
イ 正しい。クイックソートは、中間的な基準値を決めて、それよりも大きな値を集めた区分と、小さな値を集めた区分に要素を振り分け、次に、それぞれの区分の中で同様な処理を繰り返す方法である。
ウ 挿入ソートは、1つずつデータを取り出し、整列済みのデータの適切な位置に挿入する操作を繰り返す方法である。
エ 選択ソートは、残っているデータの中から一番小さいもの (もしくは大きいもの) を取り出す操作を繰り返す方法である。