バブルソートとは - 【ゆるゆるプログラミング】

Javaプログラミング

バブルソート(bubble sort)

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

バブルソートの解説

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

{ 8, 5, 4, 9, 3 } → { 3, 4, 5, 8, 9 }

説明のため配列を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[ 0 ] = 8
data[ 1 ] = 5
data[ 2 ] = 4
data[ 3 ] = 9
data[ 4 ] = 3

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

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

data[ 0 ] = 8
data[ 1 ] = 5
data[ 2 ] = 4
data[ 3 ] = 3　←　入れ替え
data[ 4 ] = 9　←　入れ替え

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

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

data[ 0 ] = 8
data[ 1 ] = 5
data[ 2 ] = 3　←　入れ替え
data[ 3 ] = 4　←　入れ替え
data[ 4 ] = 9

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

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

data[ 0 ] = 8
data[ 1 ] = 3　←　入れ替え
data[ 2 ] = 5　←　入れ替え
data[ 3 ] = 4
data[ 4 ] = 9

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

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

data[ 0 ] = 3　←　入れ替え
data[ 1 ] = 8　←　入れ替え
data[ 2 ] = 5
data[ 3 ] = 4
data[ 4 ] = 9

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

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 8
data[ 2 ] = 5
data[ 3 ] = 4
data[ 4 ] = 9

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 8
data[ 2 ] = 5
data[ 3 ] = 4　←　入れ替えない
data[ 4 ] = 9　←　入れ替えない

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 8
data[ 2 ] = 4　←　入れ替え
data[ 3 ] = 5　←　入れ替え
data[ 4 ] = 9

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　入れ替え
data[ 2 ] = 8　←　入れ替え
data[ 3 ] = 5
data[ 4 ] = 9

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

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 8
data[ 3 ] = 5
data[ 4 ] = 9

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 8
data[ 3 ] = 5　←　入れ替えない
data[ 4 ] = 9　←　入れ替えない

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 5　←　入れ替え
data[ 3 ] = 8　←　入れ替え
data[ 4 ] = 9

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 5　←　確定
data[ 3 ] = 8
data[ 4 ] = 9

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

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

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 5　←　確定
data[ 3 ] = 8　←　入れ替えない
data[ 4 ] = 9　←　入れ替えない

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 5　←　確定
data[ 3 ] = 8　←　確定
data[ 4 ] = 9

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

data[ 0 ] = 3　←　確定
data[ 1 ] = 4　←　確定
data[ 2 ] = 5　←　確定
data[ 3 ] = 8　←　確定
data[ 4 ] = 9　←　確定

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

Javaソースコード

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

BubbleSort1.java

ダウンロード

public class BubbleSort1 {
	// バブルソート(昇順)
	private static void bubble_sort( int[] data )
	{
		// 配列の要素数を代入
		int datacount = data.length;
		
		// 並び替え処理
		for ( int i = 0; i < datacount - 1; i++ ) {
			// data[ i ]の値を決める処理
			for ( int j = datacount - 1; j > i; j-- ) {
				// data[ j ]とdata[ j - 1 ]の値の入替
		        	if ( data[ j ] < data[ j - 1 ] ) {
					int temp = data[ j ];
					data[ j ] = data[ j - 1 ];
					data[ j - 1 ] = temp;
				}
			}
		}
        }

	// メイン
	public static void main( String[] args ) {
		int[] data = { 8, 5, 4, 9, 3 };

		// バブルソート
		bubble_sort( data );

		// 結果出力
		for ( int i = 0; i < data.length; ++ i )
			System.out.println( data[ i ] );
	}
}

実行

java BubbleSort1

出力結果

Javaソースコード解説

public class BubbleSort1 {

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

002
003

	// バブルソート(昇順)
	private static void bubble_sort( int[] data )

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

005
006

		// 配列の要素数を代入
		int datacount = data.length;

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

008
009

		// 並び替え処理
		for ( int i = 0; i < datacount - 1; i++ ) {

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

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

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

010
011

			// data[ i ]の値を決める処理
			for ( int j = datacount - 1; j > i; j-- ) {

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

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

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

				// data[ j ]とdata[ j - 1 ]の値の入替
		        	if ( data[ j ] < data[ j - 1 ] ) {
					int temp = data[ j ];
					data[ j ] = data[ j - 1 ];
					data[ j - 1 ] = temp;
				}

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

022
023

	// メイン
	public static void main( String[] args ) {

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

		int[] data = { 8, 5, 4, 9, 3 };

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

026
027

		// バブルソート
		bubble_sort( data );

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

029
030
031

		// 結果出力
		for ( int i = 0; i < data.length; ++ i )
			System.out.println( data[ i ] );

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

以上です。

プロになるJava?仕事で必要なプログラミングの知識がゼロから身につく最高の指南書

スッキリわかるJava入門第3版スッキリわかるシリーズ

スッキリわかるJava入門実践編第3版スッキリわかるシリーズ

ゆるゆるプログラミング

Javaプログラミング

バブルソート(bubble sort)

バブルソートの解説

Javaソースコード

実行

出力結果

Javaソースコード解説

関連コンテンツ

広告