Bubble sort

Ascending order means smallest first, going up (2, 5, 9).

Descending order means largest first, going down (9, 5, 2). Unless a question says otherwise, sorts put numbers into ascending order.

A bubble sort goes along the list comparing each pair of neighbours. If a pair is in the wrong order, it swaps them. One trip along the list is a pass.

After the first pass, the largest item has "bubbled" to the end and is in its final place. So each pass can stop one place earlier than the one before.

A worked example: the first pass of a bubble sort on 14, 9, 22, 6, 17, into ascending order.

1. Compare 14 and 9. 14 is bigger, so swap: 9, 14, 22, 6, 17.

Counting comparisons: a list of n items has n − 1 neighbouring pairs, so the first pass makes n − 1 comparisons. If each pass stops one place earlier, the second pass makes n − 2, the third n − 3, and so on.

A swap is only counted when a pair is out of order, so a pass can make fewer swaps than comparisons.

The sort repeats passes until a pass makes no swaps.

Only then does it know the list is sorted.

• A list can be in order after pass 2, but the algorithm only finds out in pass 3, which makes no swaps.
• A list of n items needs at most n − 1 passes.
• For descending order, swap when the left item is smaller. For words, compare alphabetically.

1. Write the list. Compare items 0 and 1, swap if needed, and write the list again if it changed.

Carrying on the worked example until it stops:

1. After pass 1: 9, 14, 6, 17, 22 (3 swaps).

A very common mistake is to write the fully sorted list when the question asks for the list after one pass.