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