Sorting Algorithms

1 Describe how a bubble sort sorts a list of numbers into ascending order. 4

One mark for each of the following, to a maximum of 4.

• Adjacent pairs of items are compared
• If they are in the wrong order they are swapped
• This is repeated for the whole list, which is called a pass
• Passes continue until a pass is completed with no swaps

Model answer. A bubble sort starts at the beginning of the list and compares the first two items. If they are in the wrong order it swaps them, then moves along one position and compares the next adjacent pair, continuing to the end of the list. One complete journey through the list is called a pass, and at the end of each pass the largest remaining value has been carried to its correct position at the end. The algorithm then begins another pass, and it keeps going until a whole pass is completed without a single swap being made, which shows that no pair is out of order and the list is sorted.

2 Describe how a merge sort works. 4

One mark for each of the following, to a maximum of 4.

• The list is repeatedly divided in half
• Until each sub list contains only one item
• Pairs of sub lists are then merged back together
• During each merge the smaller of the two front items is taken first, so the result stays in order

Model answer. A merge sort repeatedly divides the list in half, then divides each half in half, and continues until every sub list contains only one item, at which point every sub list is trivially in order. It then merges the sub lists back together in pairs. To merge two sub lists it compares the item at the front of each and takes whichever is smaller, repeating until one sub list is empty and then taking whatever is left in the other. Because both inputs to every merge are already sorted, the merged result is sorted too, and after the final merge the whole list is in order.

3 The list [6, 2, 9, 4] is sorted using a bubble sort. Show the contents of the list after each of the first two passes. 2

One mark for each of the following, to a maximum of 2.

• After pass 1 the list is 2, 6, 4, 9
• After pass 2 the list is 2, 4, 6, 9

Model answer. During the first pass 6 and 2 are swapped to give 2, 6, 9, 4, then 6 and 9 are left alone, then 9 and 4 are swapped, so the list after pass one is 2, 6, 4, 9. During the second pass 2 and 6 are left alone, then 6 and 4 are swapped, so the list after pass two is 2, 4, 6, 9.

4 Compare a bubble sort and a merge sort. Your answer should refer to efficiency and memory use. 6

One mark for each of the following, to a maximum of 6.

• A bubble sort repeatedly swaps adjacent items, while a merge sort divides the list and merges it back
• A merge sort is more efficient on large lists
• Because halving the list means the number of rounds grows very slowly as the list grows
• A bubble sort needs roughly n squared comparisons, so doubling the data quadruples the work
• A bubble sort uses less memory because it sorts in place
• A merge sort needs additional memory to hold the sub lists while merging

Model answer. A bubble sort works by repeatedly comparing adjacent pairs of items and swapping any that are in the wrong order, whereas a merge sort divides the list until each sub list holds one item and then merges the sub lists back together in order. On large lists a merge sort is considerably more efficient, because each round of merging halves the number of sub lists, so the number of rounds grows extremely slowly even as the list becomes very large. A bubble sort has to walk the whole list once per pass and may need almost as many passes as there are items, which means roughly n squared comparisons, so doubling the size of the list roughly quadruples the work. The trade off is memory. A bubble sort rearranges items inside the original list and so needs almost no extra memory, while a merge sort has to hold the sub lists it is building as well as the original data. For a small list, or on a device with very little memory, a bubble sort is therefore a reasonable choice, but for a large list where speed matters a merge sort is far better.

5 Explain why a bubble sort may need fewer passes on a list that is already almost in order. 3

One mark for each of the following, to a maximum of 3.

• A bubble sort stops when a pass completes with no swaps
• An almost sorted list needs few swaps, so that condition is reached quickly
• So the algorithm can finish after only one or two passes rather than n minus 1

Model answer. A bubble sort does not run a fixed number of passes. It keeps making passes until one complete pass finishes without a single swap, because that shows no adjacent pair is out of order and the list must therefore be sorted. If the list is already almost in order then very few items need swapping, so the algorithm reaches a swap free pass after only one or two passes rather than after the n minus 1 passes it would need in the worst case. This is one of the few situations in which a bubble sort performs well.