| 第２種情報処理技術者試験 |
2000年度 ＝ 平成12年度・春期 |
午前 |
問17 |
n のデータをバブルソートを使って整列するとき、データの比較回数はどれか。
| ア n
| イ n log n
| ウ n (n-1) ／ 2
| エ 2n
|
ウ
バブルソート（bubble sort）は、単純交換ソートとも呼ばれる、効率のよくない基本的なソートアルゴリズムです。
隣り合うデータを比較し、必要であれば交換を行うという一連の操作をn - 1回行います。このとき、比較回数は一回ずつ減っていきますので、全体の比較回数は、
(n - 1) + (n - 2) + … 1
です。したがって、n (n - 1) / 2回となります。
