バブルソート(bubble sort)

バブルソート

はじめに

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

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

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

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

{ 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

アルゴリズムって何?

2022.12.29

2つの変数の値を入れ替える方法を紹介しています。

2016.01.29

プログラミング、ITに関する用語をまとめています。

2022.10.17

条件式を判断して処理を分岐する方法を詳しく説明しています。

2023.03.20

プログラムの最初に実行されるメソッドは?

2022.12.13

プログラミングで使う変数って何?

2020.03.23

Javaのプログラムを書いてみませんか?プログラムの書き方をくわしく説明しています。

2020.03.23

「Javaソースコード」から実行可能な「オブジェクトコード」に変換する方法をくわしく説明しています。

2020.03.23

Javaのプログラムを作ってみませんか?プログラミングに必要なものの用意から実行までを説明しています。

2020.03.23

Javaの学習に役立つソースコードを多数紹介しています。是非、ご覧ください。

2022.09.10

Swingパッケージを使ってグラフィック表示を行う方法を解説しています。

2020.03.23

画像フォーマット形式・色・大きさ・傾きなどの変更、特定の図形(文字・記号など)を見つけたり、取り出したりする画像処理について詳しく解説。

2015.11.29

繰り返し処理を使ったJavaのソースコードサンプルを紹介しています。

2020.03.23

配列を使うJavaソースコードを多数紹介しています。

2021.05.18

数学に関係するJavaのメソッドやソースコードなどを紹介しています。

2022.10.25

三角形、台形、円などいろいろな図形の面積を計算するプログラムを紹介しています。詳しくは、記事をご覧ください。

2021.05.18

StringクラスとStringBuilderクラスを利用したプログラミングの仕方を紹介しています。

2016.12.16

Javaを使った簡単な応用プログラム(生年月日から年齢を計算プログラムなど)を紹介しています。

2022.07.07

日本で使われてきた伝統文様「和柄」について解説しています。

2022.07.27

配列に格納されている値を順番に並び替える方法を解説しています。

2019.03.11

自然数と整数って何が違う?

2020.03.23

2つの値のうち、小さい方の値と、大きい方の値を取得する方法。

2020.03.23

プログラミング言語とは?種類や特徴について説明しています。

2022.08.03

Javaプログラムの構成について解説しています。詳しくは、こちらをご覧ください。

2020.03.23

繰り返し処理の作り方を解説しています。

2016.03.02

「ゆるゆるプログラム」のコンテンツを紹介しています。興味のある方はこの記事をご覧ください。

2020.03.23

広告