Implementing Bubble Sort

As with selection sort, the method takes an int[], returns void, and sorts the array in place:

public static void bubbleSort(int[] arr) {
  // ...
}

Now let’s think about what the method has to do. When you traced it, you saw that we sorted by making a series of passes over the array. So there are two loops here. The outer loop runs the passes. The inner loop does one pass, iterating over adjacent pairs and swapping the ones that are out of order.

Let’s start with the outer loop. An array of $n$ elements needs $n-1$ passes, so we count passes with i from 0 to n - 2:

public static void bubbleSort(int[] arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    // one pass
  }
}

What does one pass do? It compares each element with the one just after it, and swaps the two if the left one is larger. We will use j for the position of the left element of the pair, so the pair is arr[j] and arr[j + 1]. Here is a pass that iterates over the whole array:

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; 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;
      }
    }
  }
}

The inner loop stops at j = n - 2, because the last pair it can look at is arr[n - 2] and arr[n - 1]. If j went one further, arr[j + 1] would be past the end of the array.

This already sorts the array. Every pass carries the largest unsettled value to the end, and there are enough passes to settle every element. But it wastes work. When you traced it, each pass looked at one fewer pair than the pass before, because we do not need to look at the settled tail. This code iterates over the settled tail every time.

Let’s fix that. When the loop body runs with a given i, i passes have already finished, so the last i slots are settled. The unsettled part is arr[0] through arr[n - 1 - i], and the last pair inside it is arr[n - 2 - i] and arr[n - 1 - i]. So the inner loop should stop at j = n - 2 - i, which means its condition is j < n - 1 - i:

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];  // swap the out-of-order pair
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

If you trace it on [5, 1, 4, 2] you will get exactly the three passes from the previous section: three pairs in the first pass, two in the second, one in the third.

The loop invariant

We shortened the inner loop because we said the settled tail is settled. That is this loop’s invariant, and it is the same one selection sort keeps: after pass i, the last i slots hold the i largest values of the array, each in its final position. When the outer loop ends, $n-1$ passes have run, so the last $n-1$ slots hold the $n-1$ largest values. The one slot left over, arr[0], has to hold the smallest value, so the whole array is sorted.