Bubble Sort with Early Termination

Plain bubble sort makes all $\frac{n(n-1)}{2}$ comparisons even on an array that is already sorted. On that input it never swaps anything. If a pass makes no swaps, then every adjacent pair it compared was already in order. An array where every adjacent pair is in order is a sorted array. So a pass with no swaps tells us we are done, and there is no reason to run any more passes.

We track whether the current pass swapped anything with a boolean flag. We set it to false at the start of each pass, flip it to true inside any swap, and check it after the pass. If it is still false, we break out of the outer loop:

public static void bubbleSort(int[] arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    boolean swapped = false;
    for (int j = 0; j < n - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];  // swap the out-of-order pair
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        swapped = true;  // remember that this pass did work
      }
    }
    if (!swapped) {
      break;  // a clean pass means the array is already sorted
    }
  }
}

Comparisons

The swaps have not changed. Every swap still removes one inversion, so the sort still makes exactly as many swaps as the input has inversions. What changed is the number of comparisons, because the sort can now stop after any pass that makes no swaps.

On an already-sorted array, the first pass makes its $n-1$ comparisons, finds every pair in order, and swaps nothing. swapped stays false and we break. That is $n-1$ comparisons and $0$ swaps, which is $O(n)$.

On a reverse-sorted array, every pass finds a pair out of order, so swapped is true after every pass and the sort never stops early. We make the full $\frac{n(n-1)}{2}$ comparisons and as many swaps, just as before. The worst case is unchanged at $O(n^2)$.

So the best case went from $O(n^2)$ to $O(n)$ and the worst case did not change. The flag is a single boolean, so the auxiliary space is still $O(1)$.

Nearly sorted input

How well does the flag do on an array that is almost sorted? That depends on which way the out-of-place elements have to move.

Take [5, 1, 2, 3, 4], sorted except for one large element at the front. The first pass compares (5, 1), (5, 2), (5, 3), (5, 4) and swaps each time, which moves the 5 to the end. The second pass compares three pairs, swaps nothing, and the sort stops. That is $4+3=7$ comparisons and $4$ swaps.

Now take [2, 3, 4, 5, 1], sorted except for one small element at the end. It has the same four inversions. The first pass swaps only the last pair, moving the 1 one slot left. The second, third, and fourth passes do the same. Every pass swaps something, so the sort never stops early, and we make all $4+3+2+1=10$ comparisons.

The reason is the direction of the passes. A pass sweeps left to right, so a large element can move all the way to the right in one pass, but a small element moves left by only one slot per pass. The number of passes is set by the element that has to move farthest to the left. If one small element sits at the end of an otherwise sorted array, that is $n-1$ passes, and the sort costs $O(n^2)$ on an input with only $n-1$ inversions.

One of the practice problems for this chapter, cocktail shaker sort, alternates the direction of the passes so that a small element does not have to move left one slot per pass.