基本情報技術者試験 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回となります。


BohYoh.comトップページへ