Understand and explain how the bubble sort algorithm works.

The idea

Bubble sort repeatedly walks through a list, comparing each neighbouring pair and swapping them when they are in the wrong order, so larger items drift towards the end of the list. After one complete pass the final item is in its correct place, so the next pass can stop one position earlier. Passes repeat until a whole pass makes no swaps, which shows the list is sorted. For example, sorting 5, 1, 4, 2: compare 5 and 1, swap to get 1, 5, 4, 2; compare 5 and 4, swap to get 1, 4, 5, 2; compare 5 and 2, swap to get 1, 4, 2, 5. The 5 is now fixed at the end. A second pass sorts the remaining three items. Explain the comparison, the swap condition, the shrinking unsorted region and the stopping rule.

What earns the marks

• States that bubble sort compares each pair of adjacent items in the list in turn.
• States that a swap occurs when the two compared items are in the wrong order (for example, the left item is greater than the right when sorting ascending).
• Explains that after each complete pass the largest remaining unsorted item has moved to the end of the unsorted region, so the region shrinks by one each pass.
• Explains that passes repeat until a full pass makes no swaps, indicating the list is sorted.
• Applies the method correctly to a short list, showing the state after each comparison or pass.

Common mistakes and how to put them right

• Thinking bubble sort compares every item with every other item at once.

  Put it right: It only compares neighbouring pairs in sequence during a pass.

• Believing the algorithm stops after a fixed number of passes regardless of the data.

  Put it right: It stops when a pass produces no swaps, which may be earlier for partly sorted data.

• Assuming the smallest item moves to the front first.

  Put it right: In an ascending sort the largest unsorted item bubbles to the end of the unsorted region each pass.

Exam tips

• Trace a short list pass by pass, writing the list after each swap so the examiner can follow your reasoning.
• State the swap condition explicitly, for example swapping when the left value is greater than the right value for ascending order.
• Link the stopping rule to 'no swaps in a complete pass' rather than to a fixed pass count.