明解 Javaによるアルゴリズムとデータ構造 6-2_バブルソート
6-2 バブルソート
概要
隣り合う2要素の大小関係を調べて必要に応じて交換を繰り返す、単純交換ソート straight exchange sort の一種。
- 要素数 n の配列に対して、n-1 回の比較・交換(この作業をパスという)を行うことで、最小要素を先頭に移動する
- 更に n-2 回の比較・交換で、2倍目に小さい要素をソートできる
- …(以下同様)
- パスを k 回行えば、先頭側 k 個の要素がソート済みとなる
液体中の気泡がぶくぶくと上に上がってくるイメージ → バブルソート!
- 隣り合う2つを交換するだけのため、安定なアルゴリズムである点に留意
計算量
合計比較回数:
合計交換回数の平均:
- (比較の半分が交換を伴うとして、) 合計比較回数 / 2 =
合計移動回数の平均:
- (swap()内で代入が3回行われるので、) 合計交換回数の平均 * 3 =
ソースコード(初版)
- ケツからソート版
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
- 解答抜粋 - BohYoh.com【著書】明解Javaによるアルゴリズムとデータ構造《演習問題6-5の解答》
- こっちのほうが終了条件スマートでいいな
//--- 双方向バブルソート(シェーカーソート)---// 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; } }
- 作者: 柴田望洋
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2007/11/07
- メディア: 単行本
- 購入: 5人 クリック: 42回
- この商品を含むブログ (19件) を見る