[バブルソート]
バブルソートはソートアルゴリズムの中で、最も単純なアルゴリズムである。
バブルソートの考え方としては、例えばn個の配列があり、その中に順番が適当な
数字が入っているとすると、まず配列の一番うしろから隣り合う要素を比較して、
前の配列に入っている数値が後ろより大きければ、前と後ろの要素を互いに交換する。
これを先頭の要素まで繰り返す。そうすると、一番小さな数字が先頭に現れるようになる。
これで先頭の要素はもう変化しないので、先頭を除いてもう1回やると今度は、
2番目に小さな数字が2番目の要素に現れる。こうしてこの操作を最後まで
繰り返すと先頭から小さい数字順に並び替わる。
また、後ろから前へデータが移動することから、泡(バブル)が浮かび上がるように
見えるので、バブルソートと呼ばれているらしい。

[サンプルプログラム]
class Sample03{
	public static void main(String args[]){
		int a[] = {9, 3, 2, 5, 6, 1, 7, 8, 0, 4};
		int t;
		for(int i = 0; i < 9; i++){
			for(int j = 9; j > i; j--){
				if(a[j-1] > a[j]){
					t = a[j];
					a[j] = a[j-1];
					a[j-1] = t;
				}
			}
		}

		System.out.println("a[0] = " + a[0]);
		System.out.println("a[1] = " + a[1]);
		System.out.println("a[2] = " + a[2]);
		System.out.println("a[3] = " + a[3]);
		System.out.println("a[4] = " + a[4]);
		System.out.println("a[5] = " + a[5]);
		System.out.println("a[6] = " + a[6]);
		System.out.println("a[7] = " + a[7]);
		System.out.println("a[8] = " + a[8]);
		System.out.println("a[9] = " + a[9]);			
	}
}

このプログラムでは、まず配列を宣言しその中に10個の要素をいれている。
まず1回目、9番目の要素(最後)から0番目(先頭)まで比較を行っている。
並び替えのの仕方はif文を使い、前の要素が後ろより大きいという条件を満たした時、
後ろの要素を適当な変数に代入しておき、前の要素を後ろにいれる。
そして、あらかじめ変数にいれておいた後ろの要素の値を前の要素に代入すればよい。
こうすれば、最終的に配列の0番目に一番小さな数字が現れる。
次に2回目は、9番目から1番目まで比較を行い、2番目に小さな数字が配列の1番目に
現れる。これを9回目まで行うと、1番最後の要素だけが整列されていないが、そこは
自動的に最大の数字になるはずなので10回目を行う必要はなく、
これで並べ替えは完了である。
このようにfor文を入れ子にすることによってバブルソートを実現することができる。

[実行結果]
a[0] = 0
a[1] = 1
a[2] = 2
a[3] = 3
a[4] = 4
a[5] = 5
a[6] = 6
a[7] = 7
a[8] = 8
a[9] = 9
	
はじめ配列の要素は 9, 3, 2, 5, 6, 1, 7, 8, 0, 4 の順番であったが
バブルソートを行い、結果のように先頭から小さい数字順に並んだ。			

戻る