Bubble Sort - Java Programming

Bubble sort repeatedly compares adjacent values and swaps them when they are out of order. It is not a production sorting choice for large data, but it is useful for learning comparison, swapping, and loop behavior.

Basic Implementation

                            Basic.java
                        
Replay: real traced execution (multi-file project)

                            public class Basic {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {64, 34, 25, 12, 22, 11, 90};

        System.out.println("Before: " + java.util.Arrays.toString(numbers));
        bubbleSort(numbers);
        System.out.println("After:  " + java.util.Arrays.toString(numbers));
    }
}

                        
1public static void main(String[] args)⋯15public static void main(String[] args) {16    int[] numbers = {64, 34, 25, 12, 22, 11, 90};1718    System.out.println("Before: " + java.util.Arrays.toString(numbers));19    bubbleSort(numbers);20    System.out.println("After:  " + java.util.Arrays.toString(numbers));⋯outputBefore: [64, 34, 25, 12, 22, 11, 90]
2n ← 71public class Basic {2    static void bubbleSort(int[] arr) {3        int n→ 7 = arr.length7;4        for (int i = 0; i < n - 1; i++) {⋯
3for (int i = 0; i < n - 1; i++)pass 1 of 6⋯3int n = arr.length;4for (int i0 = 0; i < n7 - 1; i++) {5    for (int j = 0; j < n - i - 1; j++) {⋯All 6 passes — pass 1 is the card abovepassi
10
21
32
43
54
65
4for (int j = 0; j < n - i - 1; j++)pass 1 of 21⋯4for (int i = 0; i < n - 1; i++) {5    for (int j0 = 0; j < n7 - i0 - 1; j++) {6        if (arr[j] > arr[j + 1]) {⋯21 passes — pass 1 is the card abovepassji
100
210
320
430
540
650
701
811
921
⋯ 10 more passes ⋯
2014
2105
5temp ← 64, arr[j] ← 34, arr[j + 1] ← 64pass 1 of 14⋯5for (int j = 0; j < n - i - 1; j++) {6    if (arr[j]64 > arr[j + 1]34) {7        int temp→ 64 = arr[j]64;8        arr[j]→ 34 = arr[j + 1]34;9        arr[j + 1]→ 64 = temp64;10    }⋯14 passes — pass 1 is the card abovepassjtemparr[j]arr[j + 1]
106464 → 3434 → 64
216464 → 2525 → 64
326464 → 1212 → 64
436464 → 2222 → 64
546464 → 1111 → 64
603434 → 2525 → 34
713434 → 1212 → 34
823434 → 2222 → 34
933434 → 1111 → 34
⋯ 3 more passes ⋯
1312222 → 1111 → 22
1401212 → 1111 → 12
6bubbleSort(numbers);⋯18    System.out.println("Before: " + java.util.Arrays.toString(numbers));19    bubbleSort(numbers);20    System.out.println("After:  " + java.util.Arrays.toString(numbers));21}⋯outputAfter:  [11, 12, 22, 25, 34, 64, 90]

All 6 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	4
6	5

21 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	4	0
6	5	0
7	0	1
8	1	1
9	2	1
⋯ 10 more passes ⋯
20	1	4
21	0	5

14 passes — pass 1 is the card above
pass	`j`	`temp`	`arr[j]`	`arr[j + 1]`
1	0	64	64 → 34	34 → 64
2	1	64	64 → 25	25 → 64
3	2	64	64 → 12	12 → 64
4	3	64	64 → 22	22 → 64
5	4	64	64 → 11	11 → 64
6	0	34	34 → 25	25 → 34
7	1	34	34 → 12	12 → 34
8	2	34	34 → 22	22 → 34
9	3	34	34 → 11	11 → 34
⋯ 3 more passes ⋯
13	1	22	22 → 11	11 → 22
14	0	12	12 → 11	11 → 12

Bubble Sort A comparison-based sorting algorithm that repeatedly swaps adjacent elements when they are in the wrong order.

Tracing Passes

Tracing each pass makes the loop boundaries and swap decisions visible.

                            numbers
                            numbers = {5, 2, 8, 1, 9} (default)numbers = {1, 2, 3, 4, 5}numbers = {9, 7, 5, 3, 1}
                        

                            Trace.java
                        
Replay: real traced execution (multi-file project)

                            public class Trace {
    static void bubbleSortTrace(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            System.out.println("Pass " + (i + 1) + ":");
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    System.out.printf("  Swap %d and %d%n", arr[j], arr[j + 1]);
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            System.out.println("  Result: " + java.util.Arrays.toString(arr));

            if (!swapped) {
                System.out.println("  No swaps - array is sorted!");
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {5, 2, 8, 1, 9};

        System.out.println("Initial: " + java.util.Arrays.toString(numbers));
        System.out.println();
        bubbleSortTrace(numbers);
    }
}
public class Trace {
    static void bubbleSortTrace(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            System.out.println("Pass " + (i + 1) + ":");
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    System.out.printf("  Swap %d and %d%n", arr[j], arr[j + 1]);
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            System.out.println("  Result: " + java.util.Arrays.toString(arr));

            if (!swapped) {
                System.out.println("  No swaps - array is sorted!");
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};

        System.out.println("Initial: " + java.util.Arrays.toString(numbers));
        System.out.println();
        bubbleSortTrace(numbers);
    }
}
public class Trace {
    static void bubbleSortTrace(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            System.out.println("Pass " + (i + 1) + ":");
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    System.out.printf("  Swap %d and %d%n", arr[j], arr[j + 1]);
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            System.out.println("  Result: " + java.util.Arrays.toString(arr));

            if (!swapped) {
                System.out.println("  No swaps - array is sorted!");
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers = {9, 7, 5, 3, 1};

        System.out.println("Initial: " + java.util.Arrays.toString(numbers));
        System.out.println();
        bubbleSortTrace(numbers);
    }
}

                        
1public static void main(String[] args)⋯27public static void main(String[] args) {28    int[] numbers = {5, 2, 8, 1, 9}; //@numbers={5, 2, 8, 1, 9}, {1, 2, 3, 4, 5}, {9, 7, 5, 3, 1}2930    System.out.println("Initial: " + java.util.Arrays.toString(numbers));31    System.out.println();32    bubbleSortTrace(numbers);33}⋯outputInitial: [5, 2, 8, 1, 9]
2n ← 51public class Trace {2    static void bubbleSortTrace(int[] arr) {3        int n→ 5 = arr.length5;4        for (int i = 0; i < n - 1; i++) {⋯
3swapped ← falsepass 1 of 4⋯3int n = arr.length;4for (int i0 = 0; i < n5 - 1; i++) {5    System.out.println("Pass " + (i0 + 1) + ":");6    boolean swapped→ false = false;⋯outputPass 1:All 4 passes — pass 1 is the card abovepassiswapped
10false
21false
32false
43false
4for (int j = 0; j < n - i - 1; j++)pass 1 of 10⋯8for (int j0 = 0; j < n5 - i0 - 1; j++) {9    if (arr[j] > arr[j + 1]) {⋯All 10 passes — pass 1 is the card abovepassji
100
210
320
430
501
611
721
802
912
1003
5temp ← 5, arr[j] ← 2, arr[j + 1] ← 5, swapped ← truepass 1 of 4⋯8for (int j = 0; j < n - i - 1; j++) {9    if (arr[j]5 > arr[j + 1]2) {10        System.out.printf("  Swap %d and %d%n", arr[j]5, arr[j + 1]2);11        int temp→ 5 = arr[j]5;12        arr[j]→ 2 = arr[j + 1]2;13        arr[j + 1]→ 5 = temp5;14        swapped→ true = true;15    }⋯All 4 passes — pass 1 is the card abovepassjtemparr[j]arr[j + 1]swapped
1055 → 22 → 5true
2288 → 11 → 8true
3155 → 11 → 5true
4022 → 11 → 2true
6System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [2, 5, 1, 8, 9]
7System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [2, 1, 5, 8, 9]
8System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [1, 2, 5, 8, 9]
9System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [1, 2, 5, 8, 9]
10if (!swapped)⋯20if (!swappedfalse) {21    System.out.println("  No swaps - array is sorted!");22    break;23}⋯output  No swaps - array is sorted!
11bubbleSortTrace(numbers);⋯31    System.out.println();32    bubbleSortTrace(numbers);33}⋯
1public static void main(String[] args)⋯27public static void main(String[] args) {28    int[] numbers = {1, 2, 3, 4, 5};2930    System.out.println("Initial: " + java.util.Arrays.toString(numbers));31    System.out.println();32    bubbleSortTrace(numbers);33}⋯outputInitial: [1, 2, 3, 4, 5]
2n ← 51public class Trace {2    static void bubbleSortTrace(int[] arr) {3        int n→ 5 = arr.length5;4        for (int i = 0; i < n - 1; i++) {⋯
3swapped ← false⋯3int n = arr.length;4for (int i0 = 0; i < n5 - 1; i++) {5    System.out.println("Pass " + (i0 + 1) + ":");6    boolean swapped→ false = false;⋯outputPass 1:
4for (int j = 0; j < n - i - 1; j++)pass 1 of 4⋯8for (int j0 = 0; j < n5 - i0 - 1; j++) {9    if (arr[j] > arr[j + 1]) {⋯All 4 passes — pass 1 is the card abovepassj
10
21
32
43
5System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [1, 2, 3, 4, 5]
6if (!swapped)⋯20if (!swappedfalse) {21    System.out.println("  No swaps - array is sorted!");22    break;23}⋯output  No swaps - array is sorted!
7bubbleSortTrace(numbers);⋯31    System.out.println();32    bubbleSortTrace(numbers);33}⋯
1public static void main(String[] args)⋯27public static void main(String[] args) {28    int[] numbers = {9, 7, 5, 3, 1};2930    System.out.println("Initial: " + java.util.Arrays.toString(numbers));31    System.out.println();32    bubbleSortTrace(numbers);33}⋯outputInitial: [9, 7, 5, 3, 1]
2n ← 51public class Trace {2    static void bubbleSortTrace(int[] arr) {3        int n→ 5 = arr.length5;4        for (int i = 0; i < n - 1; i++) {⋯
3swapped ← falsepass 1 of 4⋯3int n = arr.length;4for (int i0 = 0; i < n5 - 1; i++) {5    System.out.println("Pass " + (i0 + 1) + ":");6    boolean swapped→ false = false;⋯outputPass 1:All 4 passes — pass 1 is the card abovepassiswapped
10false
21false
32false
43false
4for (int j = 0; j < n - i - 1; j++)pass 1 of 10⋯8for (int j0 = 0; j < n5 - i0 - 1; j++) {9    if (arr[j] > arr[j + 1]) {⋯All 10 passes — pass 1 is the card abovepassji
100
210
320
430
501
611
721
802
912
1003
5temp ← 9, arr[j] ← 7, arr[j + 1] ← 9, swapped ← truepass 1 of 10⋯8for (int j = 0; j < n - i - 1; j++) {9    if (arr[j]9 > arr[j + 1]7) {10        System.out.printf("  Swap %d and %d%n", arr[j]9, arr[j + 1]7);11        int temp→ 9 = arr[j]9;12        arr[j]→ 7 = arr[j + 1]7;13        arr[j + 1]→ 9 = temp9;14        swapped→ true = true;15    }⋯All 10 passes — pass 1 is the card abovepassjtemparr[j]arr[j + 1]swapped
1099 → 77 → 9true
2199 → 55 → 9true
3299 → 33 → 9true
4399 → 11 → 9true
5077 → 55 → 7true
6177 → 33 → 7true
7277 → 11 → 7true
8055 → 33 → 5true
9155 → 11 → 5true
10033 → 11 → 3true
6System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [7, 5, 3, 1, 9]
7System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [5, 3, 1, 7, 9]
8System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [3, 1, 5, 7, 9]
9System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯18System.out.println("  Result: " + java.util.Arrays.toString(arr));⋯output  Result: [1, 3, 5, 7, 9]
10bubbleSortTrace(numbers);⋯31    System.out.println();32    bubbleSortTrace(numbers);33}⋯

All 4 passes — pass 1 is the card above
pass	`i`	`swapped`
1	0	false
2	1	false
3	2	false
4	3	false

All 10 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	0	1
6	1	1
7	2	1
8	0	2
9	1	2
10	0	3

All 4 passes — pass 1 is the card above
pass	`j`	`temp`	`arr[j]`	`arr[j + 1]`	`swapped`
1	0	5	5 → 2	2 → 5	true
2	2	8	8 → 1	1 → 8	true
3	1	5	5 → 1	1 → 5	true
4	0	2	2 → 1	1 → 2	true

All 4 passes — pass 1 is the card above
pass	`j`
1	0
2	1
3	2
4	3

All 4 passes — pass 1 is the card above
pass	`i`	`swapped`
1	0	false
2	1	false
3	2	false
4	3	false

All 10 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	0	1
6	1	1
7	2	1
8	0	2
9	1	2
10	0	3

All 10 passes — pass 1 is the card above
pass	`j`	`temp`	`arr[j]`	`arr[j + 1]`	`swapped`
1	0	9	9 → 7	7 → 9	true
2	1	9	9 → 5	5 → 9	true
3	2	9	9 → 3	3 → 9	true
4	3	9	9 → 1	1 → 9	true
5	0	7	7 → 5	5 → 7	true
6	1	7	7 → 3	3 → 7	true
7	2	7	7 → 1	1 → 7	true
8	0	5	5 → 3	3 → 5	true
9	1	5	5 → 1	1 → 5	true
10	0	3	3 → 1	1 → 3	true

Optimized Version

                            Optimized.java
                        
Replay: real traced execution (multi-file project)

                            public class Optimized {
    static int bubbleSortOptimized(int[] arr) {
        int n = arr.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            passes++;
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                break;
            }
        }

        return passes;
    }

    public static void main(String[] args) {
        int[] almostSorted = {1, 2, 3, 5, 4, 6, 7, 8};
        int[] reversed = {8, 7, 6, 5, 4, 3, 2, 1};

        System.out.println("Almost sorted:");
        System.out.println("Before: " + java.util.Arrays.toString(almostSorted));
        int passes1 = bubbleSortOptimized(almostSorted);
        System.out.println("After:  " + java.util.Arrays.toString(almostSorted));
        System.out.println("Passes: " + passes1);

        System.out.println("\nReverse sorted:");
        System.out.println("Before: " + java.util.Arrays.toString(reversed));
        int passes2 = bubbleSortOptimized(reversed);
        System.out.println("After:  " + java.util.Arrays.toString(reversed));
        System.out.println("Passes: " + passes2);
    }
}

                        
1public static void main(String[] args)⋯25public static void main(String[] args) {26    int[] almostSorted = {1, 2, 3, 5, 4, 6, 7, 8};27    int[] reversed = {8, 7, 6, 5, 4, 3, 2, 1};2829    System.out.println("Almost sorted:");30    System.out.println("Before: " + java.util.Arrays.toString(almostSorted));31    int passes1 = bubbleSortOptimized(almostSorted);32    System.out.println("After:  " + java.util.Arrays.toString(almostSorted));⋯outputAlmost sorted:
Before: [1, 2, 3, 5, 4, 6, 7, 8]
2n ← 8, passes ← 0pass 1 of 21public class Optimized {2    static int bubbleSortOptimized(int[] arr) {3        int n→ 8 = arr.length8;4        int passes→ 0 = 0;5        for (int i = 0; i < n - 1; i++) {⋯
3passes ← 1, swapped ← falsepass 1 of 9⋯4int passes = 0;5for (int i0 = 0; i < n8 - 1; i++) {6    passes→ 1++;7    boolean swapped→ false = false;⋯All 9 passes — pass 1 is the card abovepassipassesswapped
100 → 1false
211 → 2false
300 → 1false
411 → 2false
522 → 3false
633 → 4false
744 → 5false
855 → 6false
966 → 7false
4for (int j = 0; j < n - i - 1; j++)pass 1 of 41⋯9for (int j0 = 0; j < n8 - i0 - 1; j++) {10    if (arr[j] > arr[j + 1]) {⋯41 passes — pass 1 is the card abovepassjiswapped
100—
210—
320—
430—
540—
650—
760—
801—
911—
⋯ 30 more passes ⋯
4015—
4106—
5temp ← 5, arr[j] ← 4, arr[j + 1] ← 5, swapped ← truepass 1 of 29⋯9for (int j = 0; j < n - i - 1; j++) {10    if (arr[j]5 > arr[j + 1]4) {11        int temp→ 5 = arr[j]5;12        arr[j]→ 4 = arr[j + 1]4;13        arr[j + 1]→ 5 = temp5;14        swapped→ true = true;15    }⋯29 passes — pass 1 is the card abovepassjtemparr[j]arr[j + 1]swapped
1355 → 44 → 5true
2088 → 77 → 8true
3188 → 66 → 8true
4288 → 55 → 8true
5388 → 44 → 8true
6488 → 33 → 8true
7588 → 22 → 8true
8688 → 11 → 8true
9077 → 66 → 7true
⋯ 18 more passes ⋯
28133 → 11 → 3true
29022 → 11 → 2true
6if (!swapped)⋯16}17if (!swappedfalse) {18    break;19}⋯
7return passes;⋯22    return passes2;23}⋯
8passes1 ← 2⋯30System.out.println("Before: " + java.util.Arrays.toString(almostSorted));31int passes1→ 2 = bubbleSortOptimized(almostSorted);32System.out.println("After:  " + java.util.Arrays.toString(almostSorted));33System.out.println("Passes: " + passes12);3435System.out.println("\nReverse sorted:");36System.out.println("Before: " + java.util.Arrays.toString(reversed));37int passes2 = bubbleSortOptimized(reversed);38System.out.println("After:  " + java.util.Arrays.toString(reversed));⋯outputAfter:  [1, 2, 3, 4, 5, 6, 7, 8]
Passes: 2

Reverse sorted:
Before: [8, 7, 6, 5, 4, 3, 2, 1]
9n ← 8, passes ← 0pass 2 of 21public class Optimized {2    static int bubbleSortOptimized(int[] arr) {3        int n→ 8 = arr.length8;4        int passes→ 0 = 0;5        for (int i = 0; i < n - 1; i++) {⋯
10return passes;⋯22    return passes7;23}⋯
11passes2 ← 7⋯36    System.out.println("Before: " + java.util.Arrays.toString(reversed));37    int passes2→ 7 = bubbleSortOptimized(reversed);38    System.out.println("After:  " + java.util.Arrays.toString(reversed));39    System.out.println("Passes: " + passes27);40}⋯outputAfter:  [1, 2, 3, 4, 5, 6, 7, 8]
Passes: 7

All 9 passes — pass 1 is the card above
pass	`i`	`passes`	`swapped`
1	0	0 → 1	false
2	1	1 → 2	false
3	0	0 → 1	false
4	1	1 → 2	false
5	2	2 → 3	false
6	3	3 → 4	false
7	4	4 → 5	false
8	5	5 → 6	false
9	6	6 → 7	false

41 passes — pass 1 is the card above
pass	`j`	`i`	`swapped`
1	0	0	—
2	1	0	—
3	2	0	—
4	3	0	—
5	4	0	—
6	5	0	—
7	6	0	—
8	0	1	—
9	1	1	—
⋯ 30 more passes ⋯
40	1	5	—
41	0	6	—

29 passes — pass 1 is the card above
pass	`j`	`temp`	`arr[j]`	`arr[j + 1]`	`swapped`
1	3	5	5 → 4	4 → 5	true
2	0	8	8 → 7	7 → 8	true
3	1	8	8 → 6	6 → 8	true
4	2	8	8 → 5	5 → 8	true
5	3	8	8 → 4	4 → 8	true
6	4	8	8 → 3	3 → 8	true
7	5	8	8 → 2	2 → 8	true
8	6	8	8 → 1	1 → 8	true
9	0	7	7 → 6	6 → 7	true
⋯ 18 more passes ⋯
28	1	3	3 → 1	1 → 3	true
29	0	2	2 → 1	1 → 2	true

Early Termination If a pass makes no swaps, the array is already sorted and the algorithm can stop early.

Counting Work

Comparisons and swaps show why input order affects bubble sort.

                            ComparisonCount.java
                        
Replay: real traced execution (multi-file project)

                            public class ComparisonCount {
    static class SortStats {
        int comparisons;
        int swaps;

        SortStats(int comparisons, int swaps) {
            this.comparisons = comparisons;
            this.swaps = swaps;
        }
    }

    static SortStats bubbleSortCounted(int[] arr) {
        int n = arr.length;
        int comparisons = 0;
        int swaps = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                comparisons++;
                if (arr[j] > arr[j + 1]) {
                    swaps++;
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }

        return new SortStats(comparisons, swaps);
    }

    public static void main(String[] args) {
        int[] sorted = {1, 2, 3, 4, 5};
        int[] reversed = {5, 4, 3, 2, 1};
        int[] random = {3, 1, 4, 2, 5};

        var stats1 = bubbleSortCounted(sorted.clone());
        System.out.println("Already sorted: " + stats1.comparisons +
                         " comparisons, " + stats1.swaps + " swaps");

        var stats2 = bubbleSortCounted(reversed.clone());
        System.out.println("Reverse sorted: " + stats2.comparisons +
                         " comparisons, " + stats2.swaps + " swaps");

        var stats3 = bubbleSortCounted(random.clone());
        System.out.println("Random order:   " + stats3.comparisons +
                         " comparisons, " + stats3.swaps + " swaps");
    }
}

                        
1public static void main(String[] args)⋯31public static void main(String[] args) {32    int[] sorted = {1, 2, 3, 4, 5};33    int[] reversed = {5, 4, 3, 2, 1};34    int[] random = {3, 1, 4, 2, 5};3536    var stats1 = bubbleSortCounted(sorted.clone());37    System.out.println("Already sorted: " + stats1.comparisons + ⋯
2n ← 5, comparisons ← 0, swaps ← 0pass 1 of 3⋯12static SortStats bubbleSortCounted(int[] arr) {13    int n→ 5 = arr.length5;14    int comparisons→ 0 = 0;15    int swaps→ 0 = 0;16    for (int i = 0; i < n - 1; i++) {⋯All 3 passes — pass 1 is the card abovepassncomparisonsswaps
1500
2500
3500
3for (int i = 0; i < n - 1; i++)pass 1 of 12⋯15int swaps = 0;16for (int i0 = 0; i < n5 - 1; i++) {17    for (int j = 0; j < n - i - 1; j++) {⋯All 12 passes — pass 1 is the card abovepassi
10
21
32
43
50
61
72
83
90
101
112
123
4comparisons ← 1pass 1 of 30⋯16for (int i = 0; i < n - 1; i++) {17    for (int j0 = 0; j < n5 - i0 - 1; j++) {18        comparisons→ 1++;19        if (arr[j] > arr[j + 1]) {⋯30 passes — pass 1 is the card abovepassjicomparisons
1000 → 1
2101 → 2
3202 → 3
4303 → 4
5014 → 5
6115 → 6
7216 → 7
8027 → 8
9128 → 9
⋯ 19 more passes ⋯
29128 → 9
30039 → 10
5return new SortStats(comparisons, swaps);⋯28    return new SortStats(comparisons, swaps);29}⋯
6this.comparisons ← 10, this.swaps ← 0pass 1 of 3⋯6SortStats(int comparisons10, int swaps0) {7    this.comparisons→ 10 = comparisons10;8    this.swaps→ 0 = swaps0;9}⋯All 3 passes — pass 1 is the card abovepassswapsthis.comparisonsthis.swaps
10100
2101010
33103
7stats1 ← ⟨ComparisonCount$SortStats A⟩⋯36var stats1→ ⟨ComparisonCount$SortStats A⟩ = bubbleSortCounted(sorted.clone());37System.out.println("Already sorted: " + stats1.comparisons10 + 38                 " comparisons, " + stats1.swaps0 + " swaps");3940var stats2 = bubbleSortCounted(reversed.clone());41System.out.println("Reverse sorted: " + stats2.comparisons + ⋯outputAlready sorted: 10 comparisons, 0 swaps
8swaps ← 1, temp ← 5, arr[j] ← 4, arr[j + 1] ← 5pass 1 of 13⋯18comparisons++;19if (arr[j]5 > arr[j + 1]4) {20    swaps→ 1++;21    int temp→ 5 = arr[j]5;22    arr[j]→ 4 = arr[j + 1]4;23    arr[j + 1]→ 5 = temp5;24}⋯13 passes — pass 1 is the card abovepassjswapstemparr[j]arr[j + 1]
100 → 155 → 44 → 5
211 → 255 → 33 → 5
322 → 355 → 22 → 5
433 → 455 → 11 → 5
504 → 544 → 33 → 4
615 → 644 → 22 → 4
726 → 744 → 11 → 4
807 → 833 → 22 → 3
918 → 933 → 11 → 3
⋯ 2 more passes ⋯
1221 → 244 → 22 → 4
1312 → 333 → 22 → 3
9return new SortStats(comparisons, swaps);⋯28    return new SortStats(comparisons, swaps);29}⋯
10stats2 ← ⟨ComparisonCount$SortStats B⟩⋯40var stats2→ ⟨ComparisonCount$SortStats B⟩ = bubbleSortCounted(reversed.clone());41System.out.println("Reverse sorted: " + stats2.comparisons10 + 42                 " comparisons, " + stats2.swaps10 + " swaps");4344var stats3 = bubbleSortCounted(random.clone());45System.out.println("Random order:   " + stats3.comparisons + ⋯outputReverse sorted: 10 comparisons, 10 swaps
11return new SortStats(comparisons, swaps);⋯28    return new SortStats(comparisons, swaps);29}⋯
12stats3 ← ⟨ComparisonCount$SortStats C⟩⋯44    var stats3→ ⟨ComparisonCount$SortStats C⟩ = bubbleSortCounted(random.clone());45    System.out.println("Random order:   " + stats3.comparisons10 + 46                     " comparisons, " + stats3.swaps3 + " swaps");47}⋯outputRandom order:   10 comparisons, 3 swaps

All 3 passes — pass 1 is the card above
pass	`n`	`comparisons`	`swaps`
1	5	0	0
2	5	0	0
3	5	0	0

All 12 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3
5	0
6	1
7	2
8	3
9	0
10	1
11	2
12	3

30 passes — pass 1 is the card above
pass	`j`	`i`	`comparisons`
1	0	0	0 → 1
2	1	0	1 → 2
3	2	0	2 → 3
4	3	0	3 → 4
5	0	1	4 → 5
6	1	1	5 → 6
7	2	1	6 → 7
8	0	2	7 → 8
9	1	2	8 → 9
⋯ 19 more passes ⋯
29	1	2	8 → 9
30	0	3	9 → 10

All 3 passes — pass 1 is the card above
pass	`swaps`	`this.comparisons`	`this.swaps`
1	0	10	0
2	10	10	10
3	3	10	3

13 passes — pass 1 is the card above
pass	`j`	`swaps`	`temp`	`arr[j]`	`arr[j + 1]`
1	0	0 → 1	5	5 → 4	4 → 5
2	1	1 → 2	5	5 → 3	3 → 5
3	2	2 → 3	5	5 → 2	2 → 5
4	3	3 → 4	5	5 → 1	1 → 5
5	0	4 → 5	4	4 → 3	3 → 4
6	1	5 → 6	4	4 → 2	2 → 4
7	2	6 → 7	4	4 → 1	1 → 4
8	0	7 → 8	3	3 → 2	2 → 3
9	1	8 → 9	3	3 → 1	1 → 3
⋯ 2 more passes ⋯
12	2	1 → 2	4	4 → 2	2 → 4
13	1	2 → 3	3	3 → 2	2 → 3

Descending Order

Changing the comparison reverses the sort order.

                            Descending.java
                        
Replay: real traced execution (multi-file project)

                            public class Descending {
    static void bubbleSortAscending(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    static void bubbleSortDescending(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] < arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] numbers1 = {64, 34, 25, 12, 22};
        int[] numbers2 = {64, 34, 25, 12, 22};

        bubbleSortAscending(numbers1);
        System.out.println("Ascending:  " + java.util.Arrays.toString(numbers1));

        bubbleSortDescending(numbers2);
        System.out.println("Descending: " + java.util.Arrays.toString(numbers2));
    }
}

                        
1public static void main(String[] args)⋯28public static void main(String[] args) {29    int[] numbers1 = {64, 34, 25, 12, 22};30    int[] numbers2 = {64, 34, 25, 12, 22};3132    bubbleSortAscending(numbers1);33    System.out.println("Ascending:  " + java.util.Arrays.toString(numbers1));⋯
2n ← 51public class Descending {2    static void bubbleSortAscending(int[] arr) {3        int n→ 5 = arr.length5;4        for (int i = 0; i < n - 1; i++) {⋯
3for (int i = 0; i < n - 1; i++)pass 1 of 4⋯3int n = arr.length;4for (int i0 = 0; i < n5 - 1; i++) {5    for (int j = 0; j < n - i - 1; j++) {⋯All 4 passes — pass 1 is the card abovepassi
10
21
32
43
4for (int j = 0; j < n - i - 1; j++)pass 1 of 10⋯4for (int i = 0; i < n - 1; i++) {5    for (int j0 = 0; j < n5 - i0 - 1; j++) {6        if (arr[j] > arr[j + 1]) {⋯All 10 passes — pass 1 is the card abovepassji
100
210
320
430
501
611
721
802
912
1003
5temp ← 64, arr[j] ← 34, arr[j + 1] ← 64pass 1 of 9⋯5for (int j = 0; j < n - i - 1; j++) {6    if (arr[j]64 > arr[j + 1]34) {7        int temp→ 64 = arr[j]64;8        arr[j]→ 34 = arr[j + 1]34;9        arr[j + 1]→ 64 = temp64;10    }⋯All 9 passes — pass 1 is the card abovepassjtemparr[j]arr[j + 1]
106464 → 3434 → 64
216464 → 2525 → 64
326464 → 1212 → 64
436464 → 2222 → 64
503434 → 2525 → 34
613434 → 1212 → 34
723434 → 2222 → 34
802525 → 1212 → 25
912525 → 2222 → 25
6bubbleSortAscending(numbers1);⋯32bubbleSortAscending(numbers1);33System.out.println("Ascending:  " + java.util.Arrays.toString(numbers1));3435bubbleSortDescending(numbers2);36System.out.println("Descending: " + java.util.Arrays.toString(numbers2));⋯outputAscending:  [12, 22, 25, 34, 64]
7n ← 5⋯15static void bubbleSortDescending(int[] arr) {16    int n→ 5 = arr.length5;17    for (int i = 0; i < n - 1; i++) {⋯
8for (int i = 0; i < n - 1; i++)pass 1 of 4⋯16int n = arr.length;17for (int i0 = 0; i < n5 - 1; i++) {18    for (int j = 0; j < n - i - 1; j++) {⋯All 4 passes — pass 1 is the card abovepassijtemparr[j]arr[j + 1]
1031212 → 2222 → 12
21————
32————
43————
9for (int j = 0; j < n - i - 1; j++)pass 1 of 10⋯17for (int i = 0; i < n - 1; i++) {18    for (int j0 = 0; j < n5 - i0 - 1; j++) {19        if (arr[j] < arr[j + 1]) {⋯All 10 passes — pass 1 is the card abovepassjitemparr[j]arr[j + 1]
100———
210———
320———
4301212 → 2222 → 12
501———
611———
721———
802———
912———
1003———
10temp ← 12, arr[j] ← 22, arr[j + 1] ← 12⋯18for (int j = 0; j < n - i - 1; j++) {19    if (arr[j]12 < arr[j + 1]22) {20        int temp→ 12 = arr[j]12;21        arr[j]→ 22 = arr[j + 1]22;22        arr[j + 1]→ 12 = temp12;23    }⋯values this step3j
11bubbleSortDescending(numbers2);⋯35    bubbleSortDescending(numbers2);36    System.out.println("Descending: " + java.util.Arrays.toString(numbers2));37}⋯outputDescending: [64, 34, 25, 22, 12]

All 4 passes — pass 1 is the card above
pass	`i`
1	0
2	1
3	2
4	3

All 10 passes — pass 1 is the card above
pass	`j`	`i`
1	0	0
2	1	0
3	2	0
4	3	0
5	0	1
6	1	1
7	2	1
8	0	2
9	1	2
10	0	3

All 9 passes — pass 1 is the card above
pass	`j`	`temp`	`arr[j]`	`arr[j + 1]`
1	0	64	64 → 34	34 → 64
2	1	64	64 → 25	25 → 64
3	2	64	64 → 12	12 → 64
4	3	64	64 → 22	22 → 64
5	0	34	34 → 25	25 → 34
6	1	34	34 → 12	12 → 34
7	2	34	34 → 22	22 → 34
8	0	25	25 → 12	12 → 25
9	1	25	25 → 22	22 → 25

All 4 passes — pass 1 is the card above
pass	`i`	`j`	`temp`	`arr[j]`	`arr[j + 1]`
1	0	3	12	12 → 22	22 → 12
2	1	—	—	—	—
3	2	—	—	—	—
4	3	—	—	—	—

All 10 passes — pass 1 is the card above
pass	`j`	`i`	`temp`	`arr[j]`	`arr[j + 1]`
1	0	0	—	—	—
2	1	0	—	—	—
3	2	0	—	—	—
4	3	0	12	12 → 22	22 → 12
5	0	1	—	—	—
6	1	1	—	—	—
7	2	1	—	—	—
8	0	2	—	—	—
9	1	2	—	—	—
10	0	3	—	—	—

Sorting Strings

Bubble sort works on any comparable data when the comparison is defined.

                            Practical.java
                        
Replay: real traced execution (multi-file project)

                            public class Practical {
    static void bubbleSort(String[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    String temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            if (!swapped) break;
        }
    }

    static void bubbleSortCaseInsensitive(String[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j].compareToIgnoreCase(arr[j + 1]) > 0) {
                    String temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        String[] names = {"Charlie", "Alice", "Bob", "Diana", "Eve"};
        String[] mixed = {"apple", "Banana", "cherry", "Date"};

        System.out.println("Before: " + java.util.Arrays.toString(names));
        bubbleSort(names);
        System.out.println("After:  " + java.util.Arrays.toString(names));

        System.out.println("\nMixed case:");
        System.out.println("Before: " + java.util.Arrays.toString(mixed));
        bubbleSortCaseInsensitive(mixed);
        System.out.println("After:  " + java.util.Arrays.toString(mixed));
    }
}

                        
1public static void main(String[] args)⋯38public static void main(String[] args) {39    String[] names = {"Charlie", "Alice", "Bob", "Diana", "Eve"};40    String[] mixed = {"apple", "Banana", "cherry", "Date"};4142    System.out.println("Before: " + java.util.Arrays.toString(names));43    bubbleSort(names);44    System.out.println("After:  " + java.util.Arrays.toString(names));⋯outputBefore: [Charlie, Alice, Bob, Diana, Eve]
2n ← 51public class Practical {2    static void bubbleSort(String[] arr) {3        int n→ 5 = arr.length5;4        for (int i = 0; i < n - 1; i++) {⋯
3swapped ← falsepass 1 of 2⋯3int n = arr.length;4for (int i0 = 0; i < n5 - 1; i++) {5    boolean swapped→ false = false;⋯
4for (int j = 0; j < n - i - 1; j++)pass 1 of 7⋯7for (int j0 = 0; j < n5 - i0 - 1; j++) {8    if (arr[j].compareTo(arr[j + 1]) > 0) {⋯All 7 passes — pass 1 is the card abovepassjitemparr[j]arr[j + 1]swapped
100CharlieCharlie → AliceAlice → Charlietrue
210CharlieCharlie → BobBob → Charlietrue
320————
430———false
501————
611————
721———false
5temp ← Charlie, arr[j] ← Alice, arr[j + 1] ← Charlie, swapped ← truepass 1 of 2⋯7for (int j = 0; j < n - i - 1; j++) {8    if (arr[j]Charlie.compareTo(arr[j + 1]Alice) > 0) {9        String temp→ Charlie = arr[j]Charlie;10        arr[j]→ Alice = arr[j + 1]Alice;11        arr[j + 1]→ Charlie = tempCharlie;12        swapped→ true = true;13    }⋯values this step0j
6temp ← Charlie, arr[j] ← Bob, arr[j + 1] ← Charlie, swapped ← truepass 2 of 2⋯7for (int j = 0; j < n - i - 1; j++) {8    if (arr[j]Charlie.compareTo(arr[j + 1]Bob) > 0) {9        String temp→ Charlie = arr[j]Charlie;10        arr[j]→ Bob = arr[j + 1]Bob;11        arr[j + 1]→ Charlie = tempCharlie;12        swapped→ true = true;13    }⋯values this step1j
7swapped ← falsepass 2 of 2⋯3int n = arr.length;4for (int i1 = 0; i < n5 - 1; i++) {5    boolean swapped→ false = false;⋯
8if (!swapped)⋯16    if (!swappedfalse) break;17}⋯
9bubbleSort(names);⋯42System.out.println("Before: " + java.util.Arrays.toString(names));43bubbleSort(names);44System.out.println("After:  " + java.util.Arrays.toString(names));4546System.out.println("\nMixed case:");47System.out.println("Before: " + java.util.Arrays.toString(mixed));48bubbleSortCaseInsensitive(mixed);49System.out.println("After:  " + java.util.Arrays.toString(mixed));⋯outputAfter:  [Alice, Bob, Charlie, Diana, Eve]

Mixed case:
Before: [apple, Banana, cherry, Date]
10n ← 4⋯20static void bubbleSortCaseInsensitive(String[] arr) {21    int n→ 4 = arr.length4;22    for (int i = 0; i < n - 1; i++) {⋯
11swapped ← false⋯21int n = arr.length;22for (int i0 = 0; i < n4 - 1; i++) {23    boolean swapped→ false = false;⋯
12for (int j = 0; j < n - i - 1; j++)pass 1 of 3⋯25for (int j0 = 0; j < n4 - i0 - 1; j++) {26    if (arr[j].compareToIgnoreCase(arr[j + 1]) > 0) {⋯All 3 passes — pass 1 is the card abovepassjswapped
10—
21—
32false
13if (!swapped)⋯34    if (!swappedfalse) break;35}⋯
14bubbleSortCaseInsensitive(mixed);⋯47    System.out.println("Before: " + java.util.Arrays.toString(mixed));48    bubbleSortCaseInsensitive(mixed);49    System.out.println("After:  " + java.util.Arrays.toString(mixed));50}⋯outputAfter:  [apple, Banana, cherry, Date]

All 7 passes — pass 1 is the card above
pass	`j`	`i`	`temp`	`arr[j]`	`arr[j + 1]`	`swapped`
1	0	0	Charlie	Charlie → Alice	Alice → Charlie	true
2	1	0	Charlie	Charlie → Bob	Bob → Charlie	true
3	2	0	—	—	—	—
4	3	0	—	—	—	false
5	0	1	—	—	—	—
6	1	1	—	—	—	—
7	2	1	—	—	—	false

All 3 passes — pass 1 is the card above
pass	`j`	`swapped`
1	0	—
2	1	—
3	2	false

Exercise: Practical.java

Implement bubble sort that counts and returns the total number of swaps performed