[0156] バブルソート,比較回数

平成12年度春期 (旧)第2情報処理技術者試験より
n個のデータをバブルソートを使って整列するとき、データの比較回数はどれか。
n
n log n
2n

正解

解説

 バブルソートに関する問題です。

 バブルソートでは、片側から順に、隣り合う2つの値の大小を比較し、並べ替えを行ないます。これを、繰り返して行なうことで、並べ替えを行なうことができます。アルゴリズムは簡単ですが、比較、入れ替えの回数が非常に多くなるのが欠点です。

 それではバブルソートの例を挙げます。4 から 1 までの整数を左から小さい順に並べ替えます。何回でソートが完了するかシミュレーションしてみましょう。



 6回でソートが完了しました。データ数が4のときは、左側から行っていく比較を3順行っています。1順目では 3回の比較、2順目では 2回の比較、3順目では 1回の比較で、合計6回の比較です。

 つまり、データ個数が n のとき、比較回数は、


 (n - 1 ) + (n - 2 ) + ・・・ + 1
 =


 よって、ウが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題