バブルソート（泡立ち法）

バブルソート（泡立ち法）

 

いま仮に次のような数の列があるとする。

　　

これを小さい数から大きい数へならぶ順（昇順）の数の列に変えたいとする。

この最もシンプルな方法は、隣り合う要素の大小関係を比較し、大小が逆転していたら、隣り合う２つの要素を交換するという方法。

具体的には、まず、｛３,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が大きくなると、データの比較・交換回数が大きくなりすぎるので、実際の並び替え、ソーティングでバブルソートが使われることはない。

 

まぁ、パソコンといえども、現在は処理速度、計算速度がトンデモなく速いから、データ数が１万くらいあってもバブルソートですぐに並び終えるので、データ数が１万くらいまでならば、最も基本的なバブルソートで十分に実用に足りると思うけれど、コンピュータの能力が低かったときは、バブルソートの遅さは致命的だったんだケロよ。

 

次回は、バブルソートよりも少しだけ早くソーティングが可能になる方法を紹介するにゃ。