Searching and Sorting Algorithms

1 Describe how a binary search finds an item in a sorted list. 4

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

• The middle item of the list is examined
• If it matches the target the search stops
• If the target is smaller the upper half is discarded, if larger the lower half is discarded
• The process repeats on the remaining half until the item is found or no items remain

Model answer. Binary search begins by examining the item in the middle of the sorted list. If that item is the one being searched for, the search stops and the position is returned. If the target is smaller than the middle item then it cannot be in the upper half, so the entire upper half including the middle item is discarded. If the target is larger then the lower half is discarded instead. The process then repeats on whichever half remains, examining its middle item and discarding half again, and continues until either the item is found or the remaining range is empty, in which case the item is not in the list.

2 Show the state of the list [8, 4, 6, 2] after each pass of a bubble sort. 4

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

• After pass 1 the list is [4, 6, 2, 8]
• After pass 2 the list is [4, 2, 6, 8]
• After pass 3 the list is [2, 4, 6, 8]
• Shows that a final pass with no swaps confirms the list is sorted

Model answer. Pass 1: comparing 8 and 4 gives a swap to [4, 8, 6, 2]; comparing 8 and 6 gives a swap to [4, 6, 8, 2]; comparing 8 and 2 gives a swap to [4, 6, 2, 8]. Pass 2: comparing 4 and 6 gives no swap; comparing 6 and 2 gives a swap to [4, 2, 6, 8]; comparing 6 and 8 gives no swap. Pass 3: comparing 4 and 2 gives a swap to [2, 4, 6, 8]; the remaining comparisons give no swaps. A fourth pass makes no swaps at all, which tells the algorithm that the list is fully sorted and it stops.

3 Compare bubble sort and merge sort in terms of speed and memory use. 4

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

• Merge sort is much faster on large lists
• Bubble sort may pass through the list many times, making it very slow on large data
• Bubble sort sorts in place, using very little extra memory
• Merge sort needs additional memory to store the sub lists during merging

Model answer. In terms of speed, merge sort is substantially faster than bubble sort on large lists. Bubble sort compares every adjacent pair on each pass and may need to pass through the whole list many times, so the number of comparisons grows very steeply as the list gets longer. Merge sort repeatedly halves the problem and then merges sorted sub lists, which keeps the number of operations far lower and, importantly, gives consistent performance regardless of how disordered the original list is. The trade off is memory. Bubble sort operates in place, swapping items within the original list and needing only a single temporary variable, so its memory requirement is tiny. Merge sort has to create and hold the sub lists it produces while dividing and merging, so it requires additional memory roughly proportional to the size of the list, which can matter on devices where memory is limited.

4 A company stores 5 million customer records in a sorted list. Explain which search algorithm they should use and why. 4

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

• Recommends binary search
• The list is already sorted, which binary search requires
• Each comparison eliminates half the remaining records
• Only around 23 comparisons are needed instead of up to 5 million

Model answer. The company should use a binary search. The essential precondition is already met, because the records are stored in sorted order, and binary search cannot be used on unsorted data. Each comparison in a binary search eliminates half of the records still under consideration, so the number of items to check falls from 5 million to 2.5 million to 1.25 million and so on. This means the target is found in roughly 23 comparisons at most, since 2 to the power 23 is over 8 million. A linear search on the same data would examine records one at a time and could require up to 5 million comparisons, so the binary search is several hundred thousand times faster in the worst case, which matters enormously if searches are performed frequently.

5 Explain why an insertion sort may be a better choice than a merge sort for a small embedded device with very limited memory. 3

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

• Insertion sort works in place and requires very little extra memory
• Merge sort requires additional memory to hold sub lists
• On a device with limited memory, saving memory outweighs the speed advantage, especially for small lists

Model answer. An insertion sort operates entirely within the original list, moving items along to make space and using only a single temporary variable, so its additional memory requirement is effectively constant no matter how large the list is. A merge sort, by contrast, must create and store the sub lists it produces while dividing and merging, which requires extra memory roughly proportional to the size of the data. On an embedded device with very limited memory that extra allocation may simply not be available, and attempting it could cause the program to fail. Since embedded systems also tend to handle relatively small quantities of data, where the speed advantage of merge sort is small in absolute terms, the memory saving of insertion sort is the more important consideration.