Javaプログラミング

バブルソート(bubble sort)

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

バブルソートの解説

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

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

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

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

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

配列の最後の値data[ n - 1 ]と最後から1つ前の値data[ n - 2 ]を比較し、data[ n - 1 ] < data[ n - 2 ]の場合、data[ n - 1 ]とdata[ n - 2 ]を入れ替えます。同様に、その1つ前の値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と、最後から1つ前の値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と、1つ前の値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と、1つ前の値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と、1つ前の値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と、最後から1つ前の値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と、1つ前の値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と、1つ前の値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と、最後から1つ前の値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と、1つ前の値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と、最後から1つ前の値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

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
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

出力結果

3
4
5
8
9

Javaソースコード解説

001
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文で作成しています。

配列の最後の値は自動的にきまるので、配列要素数から1を引いた( 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までというループになります。

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

012
013
014
015
016
017
				// 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メソッドからプログラムを実行します。

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

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

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

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

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

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

関連コンテンツ

同じ型の変数(データ)を複数個まとめて管理するデータの持ちかたがあります。これが配列です。くわしくは、記事をご覧ください。

2016.01.14

処理を繰り返すために使用するfor文について解説しています。

2020.03.23

変数やクラスに格納されている値をコンソール出力する方法は?

2020.03.23

ソート(並び替え)アルゴリズムの1つであるクイックソートについて詳しく解説しています。Javaのソースコード付きです。

2019.09.06

メソッドの定義方法を詳しく解説しています。Javaのサンプルソースコードを使った説明もあります。

2020.03.23

広告