🎯

【Java】バブルソート

に公開
Java
初心者
tech

バブルソートとは

バブルソートとは、隣接する要素を比較し、必要に応じて交換を行いながら、データの並び替えを行うソートアルゴリズムです。
挿入ソート及び選択ソートと同様に、バブルソートも非効率的なアルゴリズムであり、要素数が多くなってしまうと処理が遅くなりがちです。

問題の内容と回答の方針等

  • 問題
    • サイズnの数列aをバブルソートせよ。
  • 条件
    • 配列a[]のインデックスが大きい方から隣接する要素を比較し、値が小さい方を配列の左に移動させることとする。
  • 解答方針
    • 数列aを配列a[]で管理します。
    • 外側のfor文でn-1回のループを回します。
    • i回目ではa[n-1]から順にa[i]まで比較していきます。但し、iの初期値は0とします。
    • 内側のfor文で変数jのn-1からi+1までのループを回し、a[j-1] > a[j]なら、a[j-1]とa[j]を交換します。
  • 今回の入力値
    上からn、aとする。
    4
8 1 3 2

バブルソートのコード例

import java.util.*;

public class Main {
    static void print(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            if (i > 0)
                System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
    }

    static void bubbleSort(int[] a, int n) {
        // n-1回ループする外側のfor文
        for (int i = 0; i < n - 1; i++) {
            // jがn-1からi+1までループする内側のfor文
            for (int j = n - 1; j > i; j--) {
                // a[j-1] > a[j]なら
                if (a[j - 1] > a[j]) {
                    // a[j-1]とa[j]を交換する
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
            print(a, n);
        }
    }

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

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        bubbleSort(a, n);
    }
}

バブルソートアルゴリズムの解説

バブルソートアルゴリズムに該当する下記の部分のみを解説します。

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[j]) {
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
        print(a, n);
    }
}

仮引数は下記の通りです。

a = [8, 1, 3, 2]
n = 4

i = 0 の場合

  1. 外側のfor文の条件式i=0 < n-1=3を満たすので、
  2. 内側のfor文の条件式j=3 > i=0を満たすので、
  3. if文の条件式a[2]=3 > a[3]=2を満たすので、
  4. 変数tempにa[3]の2を代入します。
  5. a[3]にa[2]の3を代入します。
  6. a[2]に変数tempの2を代入します。
    この時の配列aは下記の通りになります。
    a = [8, 1, 2, 3]
  7. jを1減らして、内側のfor文の条件式j=2 > i=0を満たすので、
  8. if文の条件式a[1]=1 > a[2]=2を満たさないので、if文を抜けます。
  9. jを1減らして、内側のfor文の条件式j=1 > i=0を満たすので、
  10. if文の条件式a[0]=8 > a[1]=1を満たすので、
  11. 変数tempにa[1]の1を代入します。
  12. a[1]にa[0]の8を代入します。
  13. a[0]に変数tempの1を代入します。
  14. この時の配列aは下記の通りになります。
    a = [1, 8, 2, 3]
  15. jを1減らして、内側のfor文の条件式j=0 > i=0を満たさないので、内側のfor文を抜けます。
  16. printメソッドを呼び出し、実引数として配列aと変数nを渡します。

i = 1 の場合

  1. 外側のfor文の条件式i=1 < n-1=3を満たすので、
  2. 内側のfor文の条件式j=3 > i=1を満たすので、
  3. if文の条件式a[2]=2 > a[3]=3を満たさないので、if文を抜けます。
  4. jを1減らして、内側のfor文の条件式j=2 > i=1を満たすので、
  5. if文の条件式a[1]=8 > a[2]=2を満たすので、
  6. 変数tempにa[2]の2を代入します。
  7. a[2]にa[1]の8を代入します。
  8. a[1]に変数tempの2を代入します。
    この時の配列aは下記の通りになります。
    a = [1, 2, 8, 3]
  9. jを1減らして、内側のfor文の条件式j=1 > i=1を満たさないので、内側のfor文を抜けます。
  10. printメソッドを呼び出し、実引数として配列aと変数nを渡します。

i = 2 の場合

  1. 外側のfor文の条件式i=2 < n-1=3を満たすので、
  2. 内側のfor文の条件式j=3 > i=2を満たすので、
  3. if文の条件式a[2]=8 > a[3]=3を満たすので、
  4. 変数tempにa[3]の3を代入します。
  5. a[3]にa[2]の8を代入します。
  6. a[2]に変数tempの3を代入します。
    この時の配列aは下記の通りになります。
    a = [1, 2, 3, 8]
  7. jを1減らして、内側のfor文の条件式j=2 > i=2を満たさないので、内側のfor文を抜けます。
  8. printメソッドを呼び出し、実引数として配列aと変数nを渡します。

Discussion