Searching and Sorting Algorithms

1 State two advantages of a binary search over a linear search on a large sorted list. 2

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

• Fewer comparisons are needed so the search is faster
• Each comparison eliminates half of the remaining items

Model answer. A binary search needs far fewer comparisons than a linear search on a large list, so it finds the item much more quickly. This is because each comparison removes half of the remaining items from the search, whereas a linear search only removes one item at a time.

2 Describe how a bubble sort would sort the list [5, 1, 4, 2] into ascending order. 4

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

• Adjacent pairs of items are compared
• They are swapped if they are in the wrong order
• This is repeated in further passes through the list
• The algorithm stops when a complete pass makes no swaps

Model answer. The algorithm compares the first two items, 5 and 1, finds them in the wrong order and swaps them to give 1, 5, 4, 2. It then compares 5 and 4, swaps them to give 1, 4, 5, 2, and compares 5 and 2, swapping them to give 1, 4, 2, 5, which completes the first pass and leaves the largest value at the end. A second pass compares 1 and 4 with no swap, then 4 and 2 with a swap, giving 1, 2, 4, 5. A third pass makes no swaps at all, and because nothing needed to move the algorithm knows the list is sorted and stops.

3 Explain how a merge sort sorts a list of numbers. 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, which is sorted by definition
• Pairs of sub lists are then merged back together
• During each merge the first item of each sub list is compared and the smaller is taken first

Model answer. A merge sort begins by dividing the list into two halves, then dividing each of those halves again, and continuing until every sub list contains exactly one item. A list of one item is already in order, which is why this is a sensible place to stop. The algorithm then merges the sub lists back together in pairs: to merge two sorted sub lists it compares the first item of each, takes whichever is smaller and places it into the new list, then repeats until both sub lists are empty. Each merge produces a longer sorted list, and the process continues until a single sorted list containing every original item remains.

4 A company stores 200000 customer records sorted by customer number. The records are searched several thousand times each day. Justify the use of a binary search rather than a linear search. 4

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

• The records are already sorted, so the requirement of binary search is met at no extra cost
• Each comparison halves the number of records still to be searched
• At most about 18 comparisons are needed instead of up to 200000
• Because the search is repeated thousands of times a day the saving is large, reducing processing time and server load

Model answer. A binary search is the right choice here because the records are already held in order of customer number, so the one condition binary search imposes is already satisfied and costs nothing to meet. Each comparison in a binary search discards half of the records still under consideration, so a file of 200000 records is reduced to one in at most about eighteen comparisons, since two to the power eighteen is greater than 200000. A linear search would in the worst case examine all 200000 records to reach the same answer. Because the search runs several thousand times a day the difference is not a technicality: it is the difference between a few tens of thousands of comparisons a day and hundreds of millions, which directly affects response time for the user and the processing load on the company's servers.

5 Compare bubble sort and merge sort, and state one situation in which each would be the better choice. 5

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

• Bubble sort repeatedly swaps adjacent items while merge sort divides and merges
• Merge sort is significantly faster on large lists
• Bubble sort uses almost no extra memory because it sorts in place
• Merge sort requires additional memory to store the sub lists
• Bubble sort is better on small or nearly sorted lists, merge sort on large lists where speed matters

Model answer. Bubble sort works by repeatedly comparing adjacent items and swapping any that are in the wrong order, continuing until a pass makes no swaps, whereas merge sort divides the list in half until each part holds one item and then merges the parts back together in order. On a large list merge sort is dramatically faster, because the number of steps grows roughly in proportion to n multiplied by the logarithm of n rather than n squared. The trade off is memory: bubble sort works in place and needs room for only a single temporary variable, while merge sort must hold the sub lists separately and so needs extra space roughly equal to the size of the original list. Bubble sort is therefore the better choice for a short list, or one that is already nearly in order, where its simplicity and low memory use matter more than raw speed, for example sorting a class of thirty test scores on a microcontroller. Merge sort is the better choice when a large volume of data must be sorted quickly and there is memory to spare, for example ordering a hundred thousand search results on a server.