計算量:O(n2)安定ソート:○バブルソートのアルゴリズムバブルソートは、「隣り合う要素を比較し、入れ替える」という考えを元にしたソートアルゴリズムです。典型的なアルゴリズムの中ではもっとも基本的で実装が簡単でです。計算量が多くなりますが、しばしば用いられます。いうデータがあります。これをバブルソートによって並び替えてみます。2乗の計算が必要になります。よって、バブルソートの計算量はO(n2)です。バブルソートの実装バブルソートを実装してみます。ソートの機能だけでなく、外ループごとに現在の並びを表示する機能や、繰り返しの回数をカウントする機能も入れています。使っていますが、この部分は最後の要素に対しては「配列の要素外」の例外が投げられていまうからです。用意し、それを介して交換します。右から左へと移動していくのが分かります。これがバブルソートという名前の由来です。実際に「交換する回数」はもっと減ります。ifの中に入れれば分かります。改良の余地バブルソートの外ループごとの結果を見れば、改良の余地があることに気づきます。それは「後半」はすべてそろっているということです。バブルソートは後ろから順にそろえていきます。そのため、「後半」はもう「隣り同士の要素を比較」する必要がないのです。重要なのは「後半」をどのように定義するか、です。逆に言えば、比較するべき「前半」の定義です。times",count);}}}内ループを見てください。これが「前半」の定義です。これにより、「前半」だけ比較し、「後半」は無視することが可能になります。実際、繰り返す回数はおおよそ半減します。この改良版バブルソートをさらに双方向で比較していくようにしたのが「シェーカーソート」です。バブルソートの発展版に「コムソート」というものもありますが、コムソートは極めて早い分、安定ソートではなくなってしまいます。