All subjects · Mathematics · WDM11 (D1)

Bubble sort: full traces and counting

Exam questions ask for complete bubble sorts in either order, with the list written after every pass and a count of comparisons and swaps.

Shortening passes

After pass 1 the last item is fixed, so pass 2 stops one place earlier, and so on. Pass k on n items makes n - k comparisons. Write the list in full at the end of every pass.

Finishing properly

You must carry out a pass with no swaps before you can say the list is sorted, even if it looks sorted already. A list of n items is in order after at most n - 1 passes.

Counting

Maximum comparisons = (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2. Maximum swaps is the same, reached when the list starts in reverse order.

Descending order

To sort into descending order, swap when the left item is smaller than the right one. Now the smallest item travels to the end in pass 1. Read the question carefully: many marks are lost by sorting the wrong way.

Worked example

Sort 14, 9, 22, 5, 17, 11, 30, 8 into ascending order with a bubble sort.

  1. After pass 1: 9, 14, 5, 17, 11, 22, 8, 30 (5 swaps)
  2. After pass 2: 9, 5, 14, 11, 17, 8, 22, 30 (3 swaps)
  3. After pass 3: 5, 9, 11, 14, 8, 17, 22, 30 (3 swaps)
  4. After pass 4: 5, 9, 11, 8, 14, 17, 22, 30 (1 swaps)
  5. After pass 5: 5, 9, 8, 11, 14, 17, 22, 30 (1 swaps)
  6. After pass 6: 5, 8, 9, 11, 14, 17, 22, 30 (1 swaps)
  7. After pass 7: 5, 8, 9, 11, 14, 17, 22, 30 (0 swaps)

Answer: Sorted after pass 7: 5, 8, 9, 11, 14, 17, 22, 30

Key idea: Pass k makes n - k comparisons; stop only after a pass with no swaps; at most n(n - 1)/2 comparisons and swaps.

Check yourself

  1. What is the maximum number of comparisons a bubble sort can make on a list of 10 items?
    Show answer

    45. n(n - 1)/2 = 10 × 9/2 = 45.

  2. In a bubble sort of 9 items, how many comparisons are made in pass 3?
    Show answer

    6. Pass k makes n - k comparisons, so pass 3 makes 9 - 3 = 6.

  3. An ascending bubble sort is applied to 14, 9, 22, 5, 17, 11, 30, 8. What is the list after pass 2?
    • 9, 14, 5, 17, 11, 22, 8, 30
    • 9, 5, 14, 11, 17, 8, 22, 30
    • 5, 9, 11, 14, 8, 17, 22, 30
    • 5, 8, 9, 11, 14, 17, 22, 30
    Show answer

    9, 5, 14, 11, 17, 8, 22, 30. Pass 1 gives 9, 14, 5, 17, 11, 22, 8, 30; pass 2 gives 9, 5, 14, 11, 17, 8, 22, 30.

  4. How many swaps does pass 1 make in the ascending bubble sort of 14, 9, 22, 5, 17, 11, 30, 8?
    Show answer

    5. Pass 1 swaps 5 times and gives 9, 14, 5, 17, 11, 22, 8, 30.

  5. How many passes in total does the bubble sort of 14, 9, 22, 5, 17, 11, 30, 8 need, including the final pass with no swaps?
    Show answer

    7. Passes 1 to 6 make swaps; pass 7 makes none, which confirms the list is sorted.

  6. A bubble sort is used to sort 23, 41, 17, 35, 29 into descending order. What is the list after pass 1?
    • 23, 17, 35, 29, 41
    • 23, 41, 35, 29, 17
    • 41, 23, 35, 29, 17
    • 41, 35, 29, 23, 17
    Show answer

    41, 23, 35, 29, 17. Swap when the left item is smaller: 23 < 41 swap; 23 > 17 keep; 17 < 35 swap; 17 < 29 swap. Result 41, 23, 35, 29, 17.

  7. A list looks sorted after pass 3 of a bubble sort. What should you do?
    • Carry out a further pass to confirm there are no swaps
    • Stop and write the list
    • Start again with a quick sort
    • Reverse the list
    Show answer

    Carry out a further pass to confirm there are no swaps. The algorithm only stops after a pass with no swaps, and examiners expect to see it.

Practise with instant feedback

Sources

Last updated 7 November 2026. Spotted a mistake? Tell us.