トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ソートの種類 > バブルソート

隣り合ったデータを比較し、逆順なら交換を繰り返すことでソートする方法。
並べ替えの過程でデータが下から上へ移動する様子が、泡が浮かんでいくように見えることから
この名前がついた。

比較回数	n(n-1)/2
交換回数	n(n-1)/4
最悪計算量	O(N^2)

3

4

2

1

6

5

の場合には、まず3と4を比較4の方が大きいのでそのまま。
次に4と2を比較。2の方が小さいので交換。

3

2

4

1

6

5

さらに4と1を交換。

3

2

1

4

6

5

4と6は交換せずにそのまま、5の方が小さいので交換すると

3

2

1

4

5

6

と最大の要素が確定する。
この処理を繰り返すことでソートする。

javaで書いてみた。私の直観で実装すると以下のような感じになるが、
一般的な実装方法はどうやら違うようだ。
それについてはバブルソート実装についてを参考にされたし。

public class Bubble {
public static void main(String[] args) {
	int[] array = { 3, 2, 4, 6, 5, 1 };
	Bubble bubble = new Bubble();
	bubble.bubble(array);
	for (int i = 0; i < array.length; i++) {
		System.out.println(array[i]);
	}
}
public void bubble(int[] array) {
	int temp;
	for (int i = 0; i < array.length; i++) {
                           /*最後の項目が確定したので配列の長さをi分縮めて同様の処理を行う*/
		for (int j = 1; j < array.length - i; j++) {
			if (array[j] < array[j - 1]) {
                                             /*以下3行は交換*/
				temp = array[j];
				array[j] = array[j - 1];
				array[j - 1] = temp;
			}
		}
	}
}
}