明解 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件) を見る
