A bubble sort is used to sort [6, 2, 9, 4, 1] into ascending order. Each pass compares adjacent pairs from the start of the list, swapping them if they are out of order. The algorithm stops after a pass in which no swaps are made. No optimisation is made to shorten later passes.
(a) Write the contents of the list at the end of each pass until the algorithm stops. [3]
(b) State the total number of comparisons made. [1]
(c) State the worst-case time complexity of bubble sort. [1]
- (a) After pass 1: [2, 6, 4, 1, 9]; after pass 2: [2, 4, 1, 6, 9](1)
- (a) After pass 3: [2, 1, 4, 6, 9]; after pass 4: [1, 2, 4, 6, 9](1)
- (a) Pass 5 makes no swaps: [1, 2, 4, 6, 9], so the algorithm stops(1)
- (b) 20 (5 passes of 4 comparisons)(1)
- (c) O(n²)(1)
- Answer: (a) [[2, 6, 4, 1, 9], [2, 4, 1, 6, 9], [2, 1, 4, 6, 9], [1, 2, 4, 6, 9], [1, 2, 4, 6, 9]] (b) 20 (c) O(n^2)
- Examiner tip: Don't forget the final pass with no swaps – that is the pass that tells the algorithm to stop, and its comparisons count.