Bubble sort

Compare arr[j] with arr[j + 1] and swap them if the left one is larger. One full pass carries the largest value to the right end, like a bubble rising.

Invariant: after pass p, the last p + 1 positions hold the largest values in their final order, so the inner loop can stop at n - 1 - pass.

1public static void bubbleSort(int[] arr) {
2    int n = arr.length;
3    for (int pass = 0; pass < n - 1; pass++) {
4        boolean swapped = false;
5        for (int j = 0; j < n - 1 - pass; j++) {
6            if (arr[j] > arr[j + 1]) {
7                int tmp = arr[j];
8                arr[j] = arr[j + 1];
9                arr[j + 1] = tmp;
10                swapped = true;
11            }
12        }
13        if (!swapped) break;           // early exit: already sorted
14    }
15}

If a whole pass makes no swaps, every neighbouring pair is in order, so the array is sorted. A swapped flag lets the algorithm stop immediately.

Without the flag, bubble sort always does n(n-1)/2 comparisons. With it, already sorted input takes a single pass of n - 1 comparisons. Run the “Already sorted” preset to see this.

Sorting [5, 1, 4, 2, 8]. Each row is one pass; ↔ marks a swap.

• Total: 9 comparisons and 4 swaps.
• 4 swaps equals the number of inversions in the input: (5,1), (5,4), (5,2), (4,2).

Every swap fixes exactly one inversion, so swaps equal the number of inversions: 0 for sorted input, n(n-1)/2 for reverse sorted input.

Comparisons are n(n-1)/2 in the worst case. With early exit, the best case is one pass.

Bubble sort swaps only when arr[j] > arr[j + 1], strictly greater. Equal neighbours are never swapped, so equal keys never pass each other and the sort is stable.

Changing the test to >= would still sort correctly but would break stability. Try the “Duplicates” preset and watch the a/b tags.