Question 1
2 marksA bubble sort is used to sort a list of 8 items.
State how many comparisons are made in the first pass, and explain how the algorithm knows when the list is sorted.
Model answer
7 comparisons: items 1 and 2, 2 and 3, and so on up to items 7 and 8. The algorithm knows the list is sorted when it completes a whole pass without making any swaps.
Explanation
A list of n items has n - 1 adjacent pairs, so a full pass makes n - 1 comparisons. The algorithm cannot see that the list is sorted; it uses a flag that records whether any swap happened during a pass, and stops when a pass makes none.
Mark scheme
-
1 mark
7
-
1 mark
when a complete pass is made with no swaps
accept 'when the swapped flag is still False at the end of a pass'. Also accept 'after 7 (n - 1) passes, because each pass puts one more item in its final place'. Do not accept 'when the list is in order' with no explanation of how this is detected.