ITパスポート試験 テクノロジ系 練習問題 第84問: 選択ソートで、n個のデータを昇順に整列する場合の比較や交換の回数に関する記述として、適切なものはどれか。

正解: 3. データが最初から昇順に並んでいても、比較の回数は減らない

選択ソートは、未整列の範囲から最小値を探し、その範囲の先頭の要素と交換する操作を繰り返す整列方法である。最小値を見つけるには未整列の要素をすべて比べる必要があるため、比較の回数はデータの並び方にかかわらず(n−1)＋(n−2)＋…＋1＝n(n−1)/2回となり、最初から昇順でも減らない。1回の走査で行う交換は多くても1回である。比較の回数はnの2乗にほぼ比例するので、nが2倍になるとおよそ4倍になる。隣り合う要素どうしだけを比べて交換するのはバブルソートである。

関連キーワード: 選択ソート・バブルソート・比較の回数・最小値