Bubble sort

How Bubble Sort Works

Bubble sort works by repeatedly stepping through the list, comparing adjacent pairs of items and swapping them if they are in the wrong order. After each full pass through the list, the largest unsorted item has "bubbled up" to its correct position at the end. This is repeated until no swaps are needed, which means the list is fully sorted.

The algorithm uses two nested loops: an outer loop that counts passes, and an inner loop that performs the adjacent comparisons within each pass. Because the last item after each pass is already in place, the inner loop can be shortened by one position each time.

The Algorithm (Pseudocode)

FOR i ← 1 TO n-1
    FOR j ← 1 TO n-i
        IF list[j] > list[j+1] THEN
            temp ← list[j]
            list[j] ← list[j+1]
            list[j+1] ← temp
        ENDIF
    ENDFOR
ENDFOR

The variable temp is needed to hold one value during the swap - without it, one value would be overwritten before it could be moved. The inner loop runs to n - i because after pass i, the last i positions are already correctly filled.

Step-by-Step: Sorting [5, 3, 8, 1, 4]

The list [5, 3, 8, 1, 4] is sorted using bubble sort below. Colour key:

Yellow Currently being compared   Red/Orange Pair swapped   Green Settled in final position   Grey Already settled - excluded from this pass

Pass 1 compares all 4 adjacent pairs in the list of 5 items.

Step 1: Compare positions 1 and 2 (5 and 3) — 5 > 3 → Swap

5 3 814
After step 1:
3 5 814

Step 2: Compare positions 2 and 3 (5 and 8) — 5 < 8 → No swap

3 5 8 14

Step 3: Compare positions 3 and 4 (8 and 1) — 8 > 1 → Swap

35 8 1 4
After step 3:
35 1 8 4

Step 4: Compare positions 4 and 5 (8 and 4) — 8 > 4 → Swap

351 8 4
After step 4 — end of Pass 1:
351 4 8 ✓

8 has bubbled to its final position. Pass 2 will ignore it.

Starting position for Pass 2: [3, 5, 1, 4, 8]

Pass 2, Step 1: Compare 3 and 5 — 3 < 5 → No swap

3 5 14 8

Pass 2, Step 2: Compare 5 and 1 — 5 > 1 → Swap

3 1 5 4 8

Pass 2, Step 3: Compare 5 and 4 — 5 > 4 → Swap — end of Pass 2

31 4 5 ✓ 8

5 is now settled. Starting Pass 3: [3, 1, 4, 5, 8]

Pass 3, Step 1: Compare 3 and 1 — 3 > 1 → Swap

1 3 4 5 8

Pass 3, Step 2: Compare 3 and 4 — 3 < 4 → No swap — end of Pass 3

1 3 4 ✓ 5 8

4 is now settled. Starting Pass 4: [1, 3, 4, 5, 8]

Starting position for Pass 4: [1, 3, 4, 5, 8]. Only the first two positions remain unsorted.

Pass 4, Step 1: Compare 1 and 3 — 1 < 3 → No swap

1 3 4 5 8

No swaps occurred in Pass 4. 3 is confirmed in position 2 and 1 in position 1.

Final sorted list:

1 ✓ 3 ✓ 4 ✓ 5 ✓ 8 ✓

When no swaps occur during an entire pass, the list must already be in order - the algorithm can stop. An optimised version of bubble sort tracks this and exits early instead of continuing unnecessary passes.

 Key Takeaways

  • Bubble sort compares adjacent pairs and swaps them if they are in the wrong order, repeating this in passes until the list is sorted.
  • After each pass, the largest unsorted item has "bubbled" to its correct position at the end of the unsorted region.
  • A swap requires a temporary variable (temp) to avoid overwriting a value before it has been moved.
  • The inner loop can be shortened by one position after each pass, since settled elements at the end do not need to be checked again.
  • If a complete pass produces no swaps, the list is fully sorted and the algorithm can stop.
  • Bubble sort is simple to understand and implement, but is less efficient than merge sort for large lists as it may require many passes.