ゆるゆるプログラミング

バブルソートは、隣り合う値の比較を繰り返して整列させるアルゴリズム(方法)です。基本交換法、隣接交換法ともよばれます。

ここで説明するバブルソートは、配列に格納されている数値を小さい方から順番に並び替えるものです。

小さい方から順番に並び替えることを昇順ソートといいいます。

以下は、配列に格納されている５つの整数を昇順ソートした結果の例です。

説明のため配列をdata、配列dataの要素数をnとします。

まず、配列の先頭の値 data[ 0 ]に、配列に格納されている最も小さい値を格納することを考えます。

配列の最後から先頭に向かって隣り合った２つのデータの大小を比較し、配列の先頭側の値が大きければ、比較した配列の値を入れ替えていきます。

配列の最後の値data[ n - 1 ]と最後から１つ前の値data[ n - 2 ]を比較し、data[ n - 1 ] < data[ n - 2 ]の場合、data[ n - 1 ]とdata[ n - 2 ]を入れ替えます。同様に、その１つ前の値data[ n - 2 ]とdata[ n - 3 ]を比較し、data[ n - 2 ] < data[ n - 3 ]の場合に値を入れ替えます。この処理を繰り返し行い、data[ 1 ]とdata[ 0 ]の比較と入れ替えを行って処理を終了します。

これで、data[ 0 ]の値は、配列の中の最小値が格納されます。

同様に、data[ 1 ]にdata[ 1 ]からdata[ n - 1 ]の中の最小値を格納、data[ 2 ]にdata[ 2 ]からdata[ n - 1 ]の中の最小値を格納、この処理をdata[ n - 2 ]まで行うと配列の値が整列します。

ここから、具体例で配列の値を使って動きを説明ししていきます。

下の例は、要素数5(n=5)の配列dataの整列前の状態を表しています。

最初に、配列の最後の値data[ 4 ]=3と、最後から１つ前の値data[ 3 ]=9の大小を比較します。

data[ 4 ] < data[ 3 ]なので、data[ 4 ]とdata[ 3 ]を入れ替えます。入れ替えた結果は以下のとおりです。

次に、data[ 3 ]=3と、１つ前の値data[ 2 ]=4の大小を比較します。

data[ 3 ] < data[ 2 ]なので、data[ 3 ]とdata[ 2 ]を入れ替えます。

同様に、data[ 2 ]=3と、１つ前の値data[ 1 ]=5の大小を比較します。

data[ 2 ] < data[ 1 ]なので、data[ 2 ]とdata[ 1 ]を入れ替えます。

同様に、data[ 1 ]=3と、１つ前の値data[ 0 ]=8の大小を比較します。

data[ 1 ] < data[ 0 ]なので、data[ 1 ]とdata[ 0 ]を入れ替えます。

これで配列の1番目の値を決める比較と入れ替えの処理は終了です。

この処理が終了した時点で、配列の先頭の値が、配列の値の最小値になります。

次に考えることは、配列の2番目の値data[ 1 ]に、data[ 1 ]からdata[ n ]の中の最小値を格納することです。

最初に、配列の最後の値data[ 4 ]=9と、最後から１つ前の値data[ 3 ]=4の大小を比較します。

data[ 4 ] < data[ 3 ]ではないので、入れ替えは行いません。

次に、data[ 3 ]=4と、１つ前の値data[ 2 ]=5の大小を比較します。

data[ 3 ] < data[ 2 ]なので、data[ 3 ]とdata[ 2 ]を入れ替えます。

次に、data[ 2 ]=4と、１つ前の値data[ 1 ]=8の大小を比較します。

data[ 2 ] < data[ 1 ]なので、data[ 2 ]とdata[ 1 ]を入れ替えます。

これで配列の2番目の値を決める比較と入れ替えの処理は終了です。

この処理が終了した時点で、配列の2番目の値data[ 1 ]が、data[ 1 ]からdata[ n ]の中の最小値になりました。

この方法で、配列の3番目、4番目、…、n-1番目の値を格納していきます。

配列の最後の値data[ 4 ]=9と、最後から１つ前の値data[ 3 ]=5の大小を比較します。

data[ 4 ] < data[ 3 ]ではないので、入れ替えは行いません。

配列のdata[ 3 ]=5と、１つ前の値data[ 2 ]=8の大小を比較します。

data[ 3 ] < data[ 2 ]なので、data[ 3 ]とdata[ 2 ]を入れ替えます。

これで配列の3番目の値を決める比較と入れ替えの処理は終了です。

配列の4番目の値を格納する処理です。

配列の最後の値data[ 4 ]=9と、最後から１つ前の値data[ 3 ]=8の大小を比較します。

data[ 4 ] < data[ 3 ]ではないので、入れ替えは行いません。

これで配列の4番目の値を決める比較と入れ替えの処理は終了です。

この配列の要素数は5なので4番目の値が決まると5番目の値も自動的に決まります。

これで並び替えの処理が終了しました。

int型の配列を昇順に並び替えるJavaのソースコードです。

クラス名を、BubbleSort1としています。

引数のint型の配列dataに格納されている値を昇順に並び替えるメソッドbubble_sortを作成しています。

配列の要素数を格納するint型の変数datacountを宣言し、配列dataの要素数を代入しています。

ここから並び替えの処理です。

配列の先頭(i=0)から順番に並び替え後の値を決めていくループをfor文で作成しています。

配列の最後の値は自動的にきまるので、配列の要素数から１を引いた( datacount - 1 )回の処理を行うループにしています。

配列の最後から先頭に向かって、隣り合った配列の値を比較させるループをfor文で作成しています。

継続条件式がj>iなので、i=0の場合はjはdatacountから1まで、i=1の場合はjはdatacountから2まで、i=2の場合はjはdatacountから3までというループになります。

これにより確定した先頭側の配列の値を比較対象から外しています。

data[ j ]とdata[ j - 1 ]の大小を比較して、data[ j ] < data[ j - 1 ]の場合に、data[ j ]とdata[ j - 1 ]の値を入れ替えています。

このmainメソッドからプログラムを実行します。

int型の配列dataに固定の５つの値を格納しています。

bubble_sortintメソッドの引数に配列を渡して値をソートしています。

配列dataの値をコンソール出力しています。

以上です。