Bubble Sort: Comparisons and Swaps

Here is bubble sort again:

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

Comparisons

The comparison is arr[j] > arr[j + 1], once per iteration of the inner loop. The first pass does $n - 1$ comparisons, the second $n - 2$ , and so on down to $1$ in the last pass. That is $\frac{n ( n - 1 )}{2}$ , the same count as selection sort, and the reason is the same. Both loops have fixed bounds and nothing inside them stops early, so the input cannot change how many comparisons happen. Even an already-sorted array costs the full $\frac{n ( n - 1 )}{2}$ comparisons. The values only decide whether a comparison is followed by a swap.

Swaps

The swaps do depend on the input. To count those swaps, it helps to name what a swap fixes.

An inversion is a pair of elements that are in the wrong order relative to each other: an element that sits to the left of a smaller element. In [5, 1, 4, 2] the inversions are $(5, 1)$ , $(5, 4)$ , $(5, 2)$ , and $(4, 2)$ , so the array has four inversions. A sorted array has none. The number of inversions measures how far from sorted an array is.

One bubble sort swap exchanges two adjacent elements that are out of order. That pair is one inversion before the swap, and after the swap it is not. No other pair changes its relative order, because the two elements only trade places with each other. So each swap removes exactly one inversion, and the array is sorted when there are none left.

That means the number of swaps bubble sort makes is exactly the number of inversions in the input. Trace it on [5, 1, 4, 2] and you will find four swaps, one per inversion.

An already-sorted array has $0$ inversions, so bubble sort makes $0$ swaps on it.
A reverse-sorted array has every pair inverted. That is $(2 n) = \frac{n ( n - 1 )}{2}$ inversions, and the same number of swaps. Every comparison is followed by a swap.
A random array has each pair inverted about half the time, so about $\frac{n ( n - 1 )}{4}$ inversions, and about that many swaps.

Running time and space

The running time is $O (n^{2})$ on every input, so the best case and the worst case are the same, as with selection sort. The two sorts differ in the swaps: selection sort never swaps more than $n - 1$ times, and bubble sort can swap $\frac{n ( n - 1 )}{2}$ times on a reverse-sorted array.

The auxiliary space is $O (1)$ : i, j, and temp.