バブルソート

Posted on Thursday, September 4th, 2014 17:15:35

100日チャレンジとして、毎日小さなプログラムを組むことにしました。まずは、ソートアルゴリズムを C で組んでみようと思います。今日はバブルソートです。

バブルソートとは

バブルソートのアルゴリズムは単純で、全ての要素を舐めていって、隣接する要素と比較して順序が逆であればスワップすることを、(要素数 – 1)回繰り返すだけの安定なソートです。そのため、最悪計算時間が O(n2) になりますが、アルゴリズムが単純なため、他のソートアルゴリズムの基礎として、始めに覚えるソートアルゴリズムとなるでしょう。

日本語では、”基本交換法”とか”隣接交換法”と言ったりしますが、”バブル”の語源はバブル全盛期に開発されたアルゴリズムだからです。なんてことは当然なくて、先頭から要素の位置が確定していく様子が泡(bubble)が浮かび上がってくるように見えることから、”バブルソート”と呼ばれるようになりました。

サンプル

ソースプログラム

実行結果

バブルソート関数の解説

解説するまでもありませんね。冒頭に書いた通り、全ての要素を舐めていって、隣接する要素と比較して順序が逆であればスワップすることを、(要素数 – 1)回繰り返すだけです。

バブルソートで行う処理は、2つのデータの比較と入れ替えだけです。以下の部分ですね。

この処理の行われる回数については単純な計算で求められます。データ数を n とすると、変数i のループの1周目は、一番小さいデータを一番上まで運ぶのに (n – 1)回(変数j のループ) の処理が行われます。変数i のループ2周目は、二番目に小さいデータを上から二番目まで運ぶのに (n – 2)回(変数j のループ) の処理が行われます。

そして、最後は二番目に大きなデータを下から二番目に運ぶのに 1回 の処理が行われます。最後に値の位置が確定していないのは、一番下と下から二番目だけですからね。下から二番目のデータまで決定すると、当然一番下のデータは動きようがありませんので処理はありません。つまり計算式としては (n – 1) + (n -2) + … + 2 + 1 となります。n(n – 1) / 2 、冒頭に書いた通り O(n²) ですね。

つまり、データの数の二乗の処理が行われるため、データ量が2倍、3倍に増えると、処理速度は4倍、9倍と増えていきます。そんな感じで、遅いけど単純で書きやすいアルゴリズムがバブルソートです。ではでは。

Share

  • このエントリーをはてなブックマークに追加
  • Pocket
  • 0 follow us in feedly

Your Message

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です