Bubble sort

Written Explanation

The idea

Stand five people in a line and ask each neighbouring pair, from left to right: "If the person on the left is taller, swap places." After one sweep the tallest person has been carried all the way to the right end, because every time they met someone shorter, they swapped forward. Repeat the sweep, and the second tallest settles next to the end, and so on.

For {4, 2, 3}:

• Compare 4 and 2: out of order, swap, giving {2, 4, 3}.
• Compare 4 and 3: out of order, swap, giving {2, 3, 4}.

One pass has moved 4, the largest, to the end. Here the array happens to be sorted already, but the algorithm does not know that yet.

The swap

Swapping two array positions needs a temporary variable. Writing a[i] = a[i + 1]; a[i + 1] = a[i]; would lose the original a[i]. The correct pattern:

int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;

The code

static void bubbleSort(int[] a) {
    for (int pass = 0; pass < a.length - 1; pass++) {
        for (int i = 0; i < a.length - 1 - pass; i++) {
            if (a[i] > a[i + 1]) {
                int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
            }
        }
    }
}

The method returns void because it changes the array it is given. The method receives the same array the caller has, not a copy, so the caller sees the sorted array. If you need the original order kept, copy the array first.

Why these bounds?

• The inner loop compares a[i] with a[i + 1], so i must stop at a.length - 2, hence i < a.length - 1 for the first pass. Without that limit the code would read past the end.
• After each pass the last pass + 1 positions already hold the largest values in their final places. The - pass makes the inner loop skip them, so it gets shorter each time.
• The outer loop needs at most a.length - 1 passes: once all but one element are in place, the last one must be in place too.

Tracing it

To trace {7, 3, 9, 1, 5}, write the array after each pass. A version of the method that prints the array and a swapped flag after each pass gives:

after pass 1: [3, 7, 1, 5, 9] swapped=true
after pass 2: [3, 1, 5, 7, 9] swapped=true
after pass 3: [1, 3, 5, 7, 9] swapped=true
after pass 4: [1, 3, 5, 7, 9] swapped=false

Reading pass 1 in detail:

The 9, the largest, is now at the end, as promised. Pass 2 does the same for the rest (excluding the last place), and so on.

Stopping early

If a whole pass makes no swaps, every neighbour pair is in order, so the array is sorted and we can stop. A boolean flag does this:

for (int pass = 0; pass < a.length - 1; pass++) {
    boolean swapped = false;
    for (int i = 0; i < a.length - 1 - pass; i++) {
        if (a[i] > a[i + 1]) {
            int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;
            swapped = true;
        }
    }
    if (!swapped) return;
}

On an array that is already sorted this finishes after a single pass.

How slow is it?

With the shrinking inner loop, the passes compare n - 1, then n - 2, and so on down to 1 pair. For 5 elements that is 4 + 3 + 2 + 1 = 10 comparisons; for 40 elements it is 780. The total grows roughly like n × n: double the data and the work about quadruples. A thousand elements already means about half a million comparisons. This is why bubble sort is a teaching tool and not a production choice.