Bubble Sort: The Idea

Here is a second way to sort. Iterate over the array from left to right, looking at each pair of neighbors. If the left one is larger than the right one, the pair is out of order, so swap them. Then move on to the next pair. When you reach the end of the array, go back to the start and do it again. Keep going until the array is sorted.

This is bubble sort. The name comes from the way large values seem to “bubble up” to the end of the array. Let’s see why by tracing it on the array [5, 1, 4, 2].

The first pass

One traversal of the array is called a pass. We start by comparing the first two elements, 5 and 1. The 5 is larger, so we swap them. The arrows mark the pair we just looked at:

┌───┬───┬───┬───┐
│ 1 │ 5 │ 4 │ 2 │
└───┴───┴───┴───┘
  ↑   ↑

Next pair: 5 and 4. The 5 is larger again, so we swap again, and the 5 moves one more slot to the right:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 5 │ 2 │
└───┴───┴───┴───┘
      ↑   ↑

Last pair: 5 and 2. One more swap, and the 5 is at the end:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 2 │ 5 │
└───┴───┴───┴───┘
          ↑   ↑

That ends the first pass. The array is not sorted yet, but look at what happened to the 5. It was the largest value in the array, so it was larger than every neighbor it was compared with, and it was swapped to the right every time. It moved all the way to the last slot.

This is true of every pass, not just this one. The largest value can start anywhere in the array. The pass reaches it and then carries it to the end. Once it is there, it is in its final position. Nothing to the left of it is larger, so no later pass moves it. We say the last slot is settled, and we shade it:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 2 │░5░│
└───┴───┴───┴───┘

The second pass

Since the last slot is settled, the second pass does not need to look at it. It iterates over the unsettled part [1, 4, 2] only.

First pair: 1 and 4. Already in order, so nothing happens:

┌───┬───┬───┬───┐
│ 1 │ 4 │ 2 │░5░│
└───┴───┴───┴───┘
  ↑   ↑

Next pair: 4 and 2. The 4 is larger, so we swap:

┌───┬───┬───┬───┐
│ 1 │ 2 │ 4 │░5░│
└───┴───┴───┴───┘
      ↑   ↑

That ends the second pass. The 4 was the largest value in the unsettled part, and the pass carried it to the end of that part, right before the 5. Now two slots are settled:

┌───┬───┬───┬───┐
│ 1 │ 2 │░4░│░5░│
└───┴───┴───┴───┘

The third pass

Only [1, 2] is left unsettled, so the third pass has one pair to look at. 1 and 2 are in order, so nothing happens, and the 2 is settled:

┌───┬───┬───┬───┐
│ 1 │░2░│░4░│░5░│
└───┴───┴───┴───┘

There is one unsettled element left, the 1. Everything to its right is larger and settled, so the 1 is in its final position too. The array is sorted.

What each pass does

Each pass carries the largest unsettled value to the end of the unsettled part and settles it there. So the settled tail grows by one slot per pass, from the right, and each pass has one fewer pair to look at than the pass before. An array of $n$ elements needs $n - 1$ passes, because after $n - 1$ elements have been settled the one left over is settled too.

A pass also puts other pairs in order. In the first pass above, only the 5 reached its final position, but the 1 moved one slot toward its final position too. Because of those other swaps, the array is often sorted before the last pass runs. In our trace, the array was sorted after the second pass, and the third pass made no swaps. Later in the chapter we will use that to stop early.

You may have noticed that the settled tail looks like the one selection sort builds: after each pass, the largest values are at the end, in their final positions. The difference is how the value gets there. Selection sort scans the unsettled part to find the largest value and moves it with a single swap. Bubble sort does not search for the largest value. It swaps neighbors that are out of order, and those swaps move the largest value to the end.