第2種情報処理技術者試験 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回となります。


BohYoh.comトップページへ