3.1.4 - Bubble sort

Comparing adjacent items

For ascending order, bubble sort compares neighboring values and swaps them if the left value is greater than the right value.

Start with [5, 1, 4, 2]. This is an array with indexes 0 to 3. A pass moves through the relevant part of the array from left to right, comparing each adjacent pair:

Use the updated array for the next comparison. After the first swap, the second pair is 5 and 4, not the original 1 and 4. By the end of this pass, the largest value, 5, has moved to its final position at the right. The rest of the array is not yet sorted: 4 still precedes 2.

A swap must preserve both original values. A temporary variable holds one value while its array position is overwritten:

temporary ← data[index]
data[index] ← data[index + 1]
data[index + 1] ← temporary

For a pair containing 5 and 1, temporary first holds 5. The left position is then set to 1, and the right position is set to the stored 5. If the final line instead used the already changed left position, both positions would contain 1 and the original 5 would be lost.

Equal adjacent values are already in an acceptable ascending order, so this version does not swap them. For descending order the comparison would be reversed, but you must follow the order specified by the task.

Tracing passes and stopping

Bubble sort needs further passes until every item is in order. After each left-to-right pass, the largest value still being processed is secured at the right-hand end of that portion.

Continuing the example, the second pass need not compare the final 5 again. It compares 1 with 4, then 4 with 2, producing [1, 2, 4, 5]. The third pass checks the remaining pair 1 and 2 and makes no swap.

An optimised version reduces the portion considered after each pass and uses a flag to detect a complete pass without swaps:

end ← LEN(data) - 1
swapped ← True
WHILE swapped AND end > 0
    swapped ← False
    index ← 0
    WHILE index < end
        IF data[index] > data[index + 1] THEN
            temporary ← data[index]
            data[index] ← data[index + 1]
            data[index + 1] ← temporary
            swapped ← True
        ENDIF
        index ← index + 1
    ENDWHILE
    end ← end - 1
ENDWHILE

end is the last index in the portion still being processed, so index < end keeps the right-hand item within that portion. At the start of a pass, swapped is reset to false. Any swap makes it true again. If an entire pass leaves it false, every adjacent pair checked is in order; with the secured items on the right, the array is sorted. The other stopping condition, end > 0, avoids a needless pass when fewer than two items remain.

Do not stop just because one comparison needs no swap. In [1, 4, 2, 5], the pair 1 and 4 is ordered, but the next pair 4 and 2 is not. A flag in a supplied algorithm may use a different name or the opposite Boolean convention: trace its actual assignments and condition.

The Python Study demonstration implements this version and prints each completed pass. The comparison counter measures adjacent-item checks, not seconds.

For the original data there are 3 + 2 + 1 = 6 comparisons. For the already sorted modification, the first pass makes three comparisons and no swaps, so the algorithm stops after that pass. A version without the early-stop flag could still perform further passes; follow the version given in an examination question.

Bubble sort is relatively straightforward to implement with a loop, an adjacent comparison and a swap. It can rearrange the existing array using only a small amount of extra storage for the temporary value and control variables. It can suit small lists, and the no-swap optimisation helps already sorted data. Its disadvantage is the many repeated comparisons and swaps that can take time on large disordered lists. Merge sort, taught next, usually handles large lists with fewer comparison stages, but requires more involved splitting and merging.