明解 Javaによるアルゴリズムとデータ構造 6-2_バブルソート

6-2 バブルソート

概要

隣り合う2要素の大小関係を調べて必要に応じて交換を繰り返す、単純交換ソート straight exchange sort の一種。

  • 素数 n の配列に対して、n-1 回の比較・交換(この作業をパスという)を行うことで、最小要素を先頭に移動する
  • 更に n-2 回の比較・交換で、2倍目に小さい要素をソートできる
  • …(以下同様)
  • パスを k 回行えば、先頭側 k 個の要素がソート済みとなる


液体中の気泡がぶくぶくと上に上がってくるイメージ → バブルソート!

  • 隣り合う2つを交換するだけのため、安定アルゴリズムである点に留意

 

計算量

合計比較回数:

  • (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}

合計交換回数の平均:

  • (比較の半分が交換を伴うとして、) 合計比較回数 / 2 = \frac{n(n-1)}{4}

合計移動回数の平均:

  • (swap()内で代入が3回行われるので、) 合計交換回数の平均 * 3 = \frac{3n(n-1)}{4}

 

ソースコード(初版)

  • ケツからソート版
import java.util.Scanner;

class BubbleSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}

	static void bubbleSort(int[] a, int n) {
		for (int i = 0; i < n - 1; i++) {
			for (int j = n - 1; j > i; j--) {
				if (a[j - 1] > a[i]) {
					swap(a, j - 1, j);
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純交換ソート(バブルソート)");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		bubbleSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[ " + i + "] = " + x[i]);
		}
	}
}
  • 頭からソート版
import java.util.Scanner;

class BubbleSortFromTop {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}

	static void bubbleSort(int[] a, int n) {
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - 1 - i; j++) {
				if (a[j] > a[j + 1]) {
					swap(a, j, j + 1);
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純交換ソート(バブルソート)");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		bubbleSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[ " + i + "] = " + x[i]);
		}
	}
}
  • 頭からソートして、途中経過を標準出力する版
import java.util.Scanner;

class BubbleSortFromTop {
	static int comparisonCnt = 0;
	static int changeCnt = 0;
	static int moveCnt = 0;

	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
		moveCnt += 3;
	}

	static void bubbleSort(int[] a, int n) {
		for (int i = 0; i < n - 1; i++) {
			System.out.println("パス" + i + ": ");
			
			//ソート途中経過
			for (int j = 0; j < n - 1 - i; j++) {
				// 比較対象でない場合はただ標準出力するだけ
				for (int k = 0; k < j; k++) {
					System.out.printf("%2d  ", a[k]);
				}
				// 比較対象であり、かつ交換される場合
				if (a[j] > a[j + 1]) {
					System.out.printf("%2d +%2d  ", a[j], a[j + 1]);
					swap(a, j, j + 1);
					for  (int k = j + 2; k < n; k++) {
						System.out.printf("%2d  ", a[k]);
					}
					System.out.print("\n");
					changeCnt++;
				// 比較対象であり、かつ交換されない場合
				} else {
					System.out.printf("%2d -%2d  ", a[j], a[j + 1]);
					for (int k = j + 2; k < n; k++) {
						System.out.printf("%2d  ", a[k]);
					}
					System.out.print("\n");
				}
				comparisonCnt++;
			}

			//交換後の一覧表示
			StringBuilder sb = new StringBuilder();
			for (int k = 1; k <= n; k++) {
				sb.append("----");
			}
			System.out.println(sb.toString());
			for (int e : a) {
				System.out.printf("%2d  ", e);
			}
			System.out.print("\n\n");
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純交換ソート(バブルソート)");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		bubbleSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[ " + i + "] = " + x[i]);
		}
		
		System.out.println();
		System.out.println("比較は " + comparisonCnt + " 回でした。");
		System.out.println("移動は " + moveCnt + " 回でした。");
		System.out.println("交換は " + changeCnt + " 回でした。");
	}
}
    • 出力結果はこんな感じ
単純交換ソート(バブルソート)
要素数: 5
x[0]:
1
x[1]:
2
x[2]:
3
x[3]:
6
x[4]:
5
パス0: 
 1 - 2   3   6   5  
 1   2 - 3   6   5  
 1   2   3 - 6   5  
 1   2   3   6 + 5  
--------------------
 1   2   3   5   6  

パス1: 
 1 - 2   3   5   6  
 1   2 - 3   5   6  
 1   2   3 - 5   6  
--------------------
 1   2   3   5   6  

パス2: 
 1 - 2   3   5   6  
 1   2 - 3   5   6  
--------------------
 1   2   3   5   6  

パス3: 
 1 - 2   3   5   6  
--------------------
 1   2   3   5   6  

昇順にソートしました
x[ 0] = 1
x[ 1] = 2
x[ 2] = 3
x[ 3] = 5
x[ 4] = 6

比較は 10 回でした。
移動は 3 回でした。
交換は 1 回でした。

ソースコード(第2版)

打ち切りを導入
あるパス内で、一度も交換が行われない  ⇒ ソートは完了している
  • パス内での交換回数を記録するローカル変数を追加
static void bubbleSort(int[] a, int n) {
	for (int i = 0; i < n - 1; i++) {
		int exchg = 0;
		for (int j = n - 1; j > i; j--) {
			if (a[j - 1] > a[j]) {
				swap(a, j - 1, j);
				exchg++;
			}
		}
		if (exchg == 0) {
			break;
		}
	}
}
  • 途中経過表示版
import java.util.Scanner;

class BubbleSort2 {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}

	static void bubbleSort(int[] a, int n) {
		// パスのループ
		for (int i = 0; i < n - 1; i++) {
			int exchg = 0;
			System.out.println("パス : " + i);
			
			// パス内での、隣接要素比較のループ
			for (int j = n - 1; j > i; j--) {
				// 比較対象要素の直前までを標準出力
				for (int k = 0; k < j - 1; k++) {
					System.out.printf("%2d  ", a[k]);
				}
				if (a[j - 1] > a[j]) {
					System.out.printf("%2d +%2d  ", a[j-1], a[j]); // 交換前の比較対象要素を出力
					for (int k = j + 1; k < n; k++) {
						System.out.printf("%2d  ", a[k]);
					}
					System.out.println();
					swap(a, j - 1, j);
					exchg++;
				} else {
					System.out.printf("%2d -%2d  ", a[j-1], a[j]); // 交換前の比較対象要素を出力
					for (int k = j + 1; k < n; k++) {
						System.out.printf("%2d  ", a[k]);
					}
					System.out.println();
				}
			}
			if (exchg == 0) {
				break;
			}
			for (int e : a) {
				System.out.printf("%2d  ", e); // パス完了時の並びを出力
			}
			System.out.print("\n\n");
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純交換ソート(バブルソート)");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		bubbleSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "] = " + x[i]);
		}
	}
}
単純交換ソート(バブルソート)
要素数: 5
x[0]:
9
x[1]:
1
x[2]:
5
x[3]:
8
x[4]:
4
パス : 0
 9   1   5   8 + 4  
 9   1   5 + 4   8  
 9   1 - 4   5   8  
 9 + 1   4   5   8  
 1   9   4   5   8  

パス : 1
 1   9   4   5 - 8  
 1   9   4 - 5   8  
 1   9 + 4   5   8  
 1   4   9   5   8  

パス : 2
 1   4   9   5 - 8  
 1   4   9 + 5   8  
 1   4   5   9   8  

パス : 3
 1   4   5   9 + 8  
 1   4   5   8   9  

昇順にソートしました
x[0] = 1
x[1] = 4
x[2] = 5
x[3] = 8
x[4] = 9

ソースコード(第3版)

前パスで既にソート済みの要素比較をスキップ
static void bubbleSort(int[] a, int n) {
	int k = 0; // ソート済インデックスのマーカー(パスをまたぐ変数)
	while (k < n - 1) {
		int last = n - 1; // 前パスで最後に交換したインデックス
		for (int j = n - 1; j > k; j--) {
			if (a[j - 1] > a[j]) {
				swap(a, j - 1, j);
				last = j;
			}
		}
		k = last;
	}
}
疑問
  • line8 と line11 でそれぞれ代入する意味ってなんだ?
    • k に逐次 j 突っ込むんじゃダメだっけ?
static void bubbleSort(int[] a, int n) {
	int k = 0; // ソート済インデックスのマーカー(パスをまたぐ変数)
	while (k < n - 1) {
		for (int j = n - 1; j > k; j--) {
			if (a[j - 1] > a[j]) {
				swap(a, j - 1, j);
				k = j;
			}
		}
	}
}
回答
  • 挙動正しく理解できてなかった。
    • for 内で k = j 突っ込んじゃうと、swap対象な j の場合、forから即出ちゃうね・・・
    • k は漸減していくパラメータであり、1パス完走した時の最小値が意味を持つ。
    • よって、for ループに関係しない変数で j を確保しといて、for ループ回りきった後に、その最小値を k に代入する仕組みが必要。
途中経過表示版
import java.util.Scanner;

class BubbleSort3 {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}

	static void bubbleSort(int[] a, int n) {
		int k = 0; // ソート済インデックスのマーカー(パスをまたぐ変数)
		while (k < n - 1) {
			System.out.println("パス: " + (k+1));
			int last = n - 1; // 最後に交換したインデックス

			for (int j = n - 1; j > k; j--) {

				// 比較対象以前の要素を表示
				for (int l = 0; l < j - 1; l++) {
					System.out.printf("%2d  ", a[l]);
				}

				// 比較
				if (a[j - 1] > a[j]) {
					// 交換対象箇所を表示
					System.out.printf("%2d +%2d  ", a[j-1], a[j]);
					swap(a, j - 1, j);
					last = j;

				} else {
					// 非交換対象箇所を表示
					System.out.printf("%2d -%2d  ", a[j-1], a[j]);
				}

				// 比較対象箇所以降の要素を表示
				for (int l = j + 1; l < n; l++) {
					System.out.printf("%2d  ", a[l]);
				}
				System.out.println();
			}
			for (int e : a) {
				System.out.printf("%2d  ", e);
			}
			System.out.println();
			k = last;
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純交換ソート(バブルソート)");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		bubbleSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "] = " + x[i]);
		}
	}
}
単純交換ソート(バブルソート)
要素数: 5
x[0]:
1
x[1]:
2
x[2]:
3
x[3]:
5
x[4]:
4
パス: 1
 1   2   3   5 + 4  
 1   2   3 - 4   5  
 1   2 - 3   4   5  
 1 - 2   3   4   5  
 1   2   3   4   5  
昇順にソートしました
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
x[4] = 5

双方向バブルソート bidirection bubble sort / シェーカーソート shaker sort

  • 『最小要素を先頭側に』と『最大要素を末尾側に』を組み合わせたソート法
    • ほぼほぼソートされているが、大きめの値がぽつんと先頭付近にあったりする際(あるいはその逆)の場合有効
ソースコード
  • shakerSort()がデブっててかっこ悪いので、あれな感じだな
import java.util.Scanner;

class ShakerSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}

	static void shakerSort(int[] a, int n) {
		int k = 0; // ソート済インデックスのマーカー
		int l = n - 1; // ソート済インデックスのマーカー
		int pathNo = 1; // 現在のパス数
		boolean topSorted = false; // トップソートの完了フラグ
		boolean bottomSorted = false; // ボトムソートの完了フラグ
		
		while (!topSorted && !bottomSorted) {
			System.out.println("パス: " + pathNo);

			// 奇数パス -> 最小値を先頭へ
			if (pathNo % 2 == 1) {
				int last = n - 1; // 最後に交換したインデックス
				for (int j = n - 1; j > k; j--) {
					// 比較対象以前の要素を表示
					for (int m = 0; m < j - 1; m++) {
						System.out.printf("%2d  ", a[m]);
					}
					// 比較
					if (a[j - 1] > a[j]) {
						// 交換対象箇所を表示
						System.out.printf("%2d +%2d  ", a[j - 1], a[j]);
						swap(a, j - 1, j);
						last = j;
					} else {
						// 非交換対象箇所を表示
						System.out.printf("%2d -%2d  ", a[j - 1], a[j]);
					}
					// 比較対象箇所以降の要素を表示
					for (int m = j + 1; m < n; m++) {
						System.out.printf("%2d  ", a[m]);
					}
					System.out.println();
				}
				k = last;

			// 偶数パス -> 最大値を末尾へ
			} else {
				int last = 0; // 最後に交換したインデックス
				for (int j = 0; j < n - k; j++) {
					// 比較対象以前の要素を表示
					for (int m = 0; m < j; m++) {
						System.out.printf("%2d  ", a[m]);
					}
					// 比較
					if (a[j] > a[j + 1]) {
						// 交換対象箇所を表示
						System.out.printf("%2d +%2d  ", a[j], a[j + 1]);
						swap(a, j, j + 1);
						last = j;
					} else {
						// 非交換対象箇所を表示
						System.out.printf("%2d -%2d  ", a[j], a[j + 1]);
					}
					// 比較対象箇所以降の要素を表示
					for (int m = j + 2; m < n; m++) {
						System.out.printf("%2d  ", a[m]);
					}
					System.out.println();
				}
				l = last;
				
			}

			// 各パスでのソート結果表示
			for (int e : a) {
				System.out.printf("%2d  ", e);
			}
			System.out.println();

			// ボトムソート・トップソート完了判定
			if (k >= n - 1)
				topSorted = true;
			if (l <= 1) {
				bottomSorted = true;
			}
			
			pathNo++;
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純交換ソート(バブルソート)");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		shakerSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "] = " + x[i]);
		}
	}
}
参考) 第三版とシェーカーソートとの差分
  • 第三版
単純交換ソート(バブルソート)
要素数: 7
x[0]:
9
x[1]:
1
x[2]:
3
x[3]:
4
x[4]:
6
x[5]:
7
x[6]:
8
パス: 1
 9   1   3   4   6   7 - 8  
 9   1   3   4   6 - 7   8  
 9   1   3   4 - 6   7   8  
 9   1   3 - 4   6   7   8  
 9   1 - 3   4   6   7   8  
 9 + 1   3   4   6   7   8  
 1   9   3   4   6   7   8  
パス: 2
 1   9   3   4   6   7 - 8  
 1   9   3   4   6 - 7   8  
 1   9   3   4 - 6   7   8  
 1   9   3 - 4   6   7   8  
 1   9 + 3   4   6   7   8  
 1   3   9   4   6   7   8  
パス: 3
 1   3   9   4   6   7 - 8  
 1   3   9   4   6 - 7   8  
 1   3   9   4 - 6   7   8  
 1   3   9 + 4   6   7   8  
 1   3   4   9   6   7   8  
パス: 4
 1   3   4   9   6   7 - 8  
 1   3   4   9   6 - 7   8  
 1   3   4   9 + 6   7   8  
 1   3   4   6   9   7   8  
パス: 5
 1   3   4   6   9   7 - 8  
 1   3   4   6   9 + 7   8  
 1   3   4   6   7   9   8  
パス: 6
 1   3   4   6   7   9 + 8  
 1   3   4   6   7   8   9  
昇順にソートしました
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9
  • シェイカー
単純交換ソート(バブルソート)
要素数: 7
x[0]:
9
x[1]:
1
x[2]:
3
x[3]:
4
x[4]:
6
x[5]:
7
x[6]:
8
パス: 1
 9   1   3   4   6   7 - 8  
 9   1   3   4   6 - 7   8  
 9   1   3   4 - 6   7   8  
 9   1   3 - 4   6   7   8  
 9   1 - 3   4   6   7   8  
 9 + 1   3   4   6   7   8  
 1   9   3   4   6   7   8  
パス: 2
 1 - 9   3   4   6   7   8  
 1   9 + 3   4   6   7   8  
 1   3   9 + 4   6   7   8  
 1   3   4   9 + 6   7   8  
 1   3   4   6   9 + 7   8  
 1   3   4   6   7   9 + 8  
 1   3   4   6   7   8   9  
パス: 3
 1   3   4   6   7   8 - 9  
 1   3   4   6   7 - 8   9  
 1   3   4   6 - 7   8   9  
 1   3   4 - 6   7   8   9  
 1   3 - 4   6   7   8   9  
 1   3   4   6   7   8   9  
パス: 4
 1 - 3   4   6   7   8   9  
 1   3   4   6   7   8   9  
昇順にソートしました
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9
//--- 双方向バブルソート(シェーカーソート)---//
static void shakerSort(int[] a, int n) {
	int left = 0;
	int right = n - 1;
	int last = right;

	 while (left < right){
		for (int j = right; j > left; j--){
			if (a[j - 1] > a[j]){
				swap(a, j - 1, j);
				last = j;
			}
		}
		left = last;

		for (int j = left; j < right; j++){
			if (a[j] > a[j + 1]){
				swap(a, j, j + 1);
				last = j;
			}
		}
		right = last;
	}
}
明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造