バブルソート（泡立ち法）
いま仮に次のような数の列があるとする。
これを小さい数から大きい数へならぶ順（昇順）の数の列に変えたいとする。
この最もシンプルな方法は、隣り合う要素の大小関係を比較し、大小が逆転していたら、隣り合う２つの要素を交換するという方法。
具体的には、まず、｛３,2,1｝の（3,2）を比較する。３と２の大小関係が逆転しているので、３と２を交換し(2,3)にする。すると、
になる。
次に、｛２,3,１｝の（3,1）の大小関係を比較すると、順序が逆転しているので、３と１を交換し、（1,3）にする。
すると、
になる。
これで、最も大きい３を右端に並べられことができた。
ということで、｛２,1,３｝の部分列、部分集合
の要素を昇順に並べ替えればいいだろう。
（２,1）を比較すると、これは順序が逆転しているので順序を交換し、（1,2）にすると、
になる。
以上のことをまとめると、
と、隣り合う要素の大小関係を比較し、順序が逆転していたら両者を交換することによって、｛３,２,１｝を昇順に｛１,２,3｝にできる。
こういう数の列の並び替えをバブルソート（泡立ち法）という。
では、もっと複雑な
の場合について考える。
(4,2)は順序が逆転しているので、２つの要素を交換すると、
になる。
次に、（４,５）を比較すると、この順序は逆転していないので、交換せずにそのまま。
次に、（５,1）を比較すると、順序が逆転しているので、交換する。
次に、（５,３）を比較すると、順序が逆転しているので、２つの要素を交換する。
これで最も大きな５が右端に並べられた。
というわけで、今度は、
を同様に昇順に並べ替えればよい。
{2,4,1,3}→{2,4,1,3}→{2,1,4,3}→{2,1,3,4}
これで、最大の４を右端に持ってくることができたので、４を取り除いた部分集合
{2,1,3}
を同様に並び替えると、
{2,1,3}→{1,2,3}→{1,2,3}
になる。
これですべて昇順に並び替えることができたのだけれど、{1,2,3}の最大値３を取り除いた部分集合
{1,2}
を昇順に並び替える。
{1,2}→{1,2}
これで並び替えの作業はおしまい。
これで、{2,4,5,1,3}を昇順に{1,2,3,4,5}と並び替えることができた。
さらに一般的につぎのような数の列、集合があるとする。
これを昇順に並び替える方法、アルゴリズムは次のようなものになるだろう。
do i=n、n−1,n−2、・・・,2
do j=1,2,・・・,i−1
a(j)とa(j+1)の大小を比較してa(j)とa(j+1)を交換
end do j
end do i
フォートラン的な記述ですが・・・。
これを元にFortranのプログラムを作ると、次のようになる。
! バブルソート
parameter(n=5)
integer a(n)
integer dummy
a(1)=4; a(2)=2; a(3) = 5; a(4)=1; a(5)=3
do i=n, 2, -1
do j=1,i-1
if (a(j).gt.a(j+1)) then !順序が逆転していたら交換
dummy = a(j)
a(j)=a(j+1)
a(j+1)=dummy
end if
end do
end do
write(*,*) a
end
バブルソートを用いると、昇順にデータを並び替えられるのですが、この方法は、データの比較・交換の回数が最悪、
約n²/2回。
n=100ならば最悪5000回、n=1000ならば５０万回、n=1万ならば５千万回と、データの数nが大きくなると、データの比較・交換回数が大きくなりすぎるので、実際の並び替え、ソーティングでバブルソートが使われることはない。
まぁ、パソコンといえども、現在は処理速度、計算速度がトンデモなく速いから、データ数が１万くらいあってもバブルソートですぐに並び終えるので、データ数が１万くらいまでならば、最も基本的なバブルソートで十分に実用に足りると思うけれど、コンピュータの能力が低かったときは、バブルソートの遅さは致命的だったんだケロよ。
次回は、バブルソートよりも少しだけ早くソーティングが可能になる方法を紹介するにゃ。