計算に時間がかかるけど勉強必須「バブルソート」とは?

  • 2016/08/09 14:42:47
目次
  • 1:バブルソートのアルゴリズム
  • 2:バブルソートの利点と欠点

バブルソートは単純交換法とも呼ばれるソートアルゴリズムです。単純選択法と同じくあまり計算効率は良くないのですが、仕組みが簡単で実装が容易です。

このアルゴリズムからはさまざまな派生アルゴリズムが生まれています。そのため基礎としてバブルソートを知っておいたほうが良いと言われています。

バブルソートのアルゴリズム

今回の例では以下の数値の配列をソートしたいものとします。

bs1

バブルソートでは2つの値の大小関係を調べて入れ替えを行います。

先ず先頭の13と8です。

bs5

13は右にいる8より大きいので並び替えが発生します。 並び替えをすると以下のようになります。

bs4

今度は13と89です。89の方が大きいので並び替えは発生しません。

次に89と45を比較します。ここでは45が小さいので並び替えが発生します

bs6

並び替えると以下のようになります。

bs3-2

このように大きい数を順に右に送っていく(もしくは小さい数を左に送る)形になります。同じく処理を続けていくと…

bs7

このように昇順でソートすることができました。図で表すようにすべての値で何度も比較交換を行わなければならないので、あまり計算効率が良くないことがイメージしていただけるかと思います。

バブルソートの利点と欠点

バブルソートは仕組みが簡単で実装が容易なことが上げられます。また冒頭で説明したとおり、バブルソートはさまざまな派生ソートアルゴリズムを生んでおり(シェーカーソート、奇偶転置ソート、コムソート、ノームソートなど)プログラミング初学者が特に勉強すべきアルゴリズムの1つと言われています。

このアルゴリズムは安全ソートです。

また全部の値を交換対象にするのであれば先頭から順番に処理を行わなくても良いアルゴリズムの為、並列処理と馴染みやすいと言われています。

しかし計算効率はソートアルゴリズムの中でも最低の部類の為、処理速度が必要な場合や配列の要素が多い場合には向いていない可能性があります。