Searching and Sorting Algorithms

1 The list shown is sorted. Describe the steps a binary search takes to find the value 28. 4

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

• Finds the middle item, which is 17
• Compares 28 with 17 and discards the lower half because 28 is larger
• Takes the middle of the remaining items, which is 28
• Compares and finds 28, so the search is complete

Model answer. The middle item of the seven is 17, at position 3. 28 is larger than 17, so the lower half and 17 itself are discarded, leaving 22, 28 and 35. The middle of those is 28, which matches, so the search stops and reports that 28 is at position 5.

2 Write a Python function called linear_search that takes a list and a target and returns the position of the target in the list, or -1 if it is not in the list. 4

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

• Defines a function with two parameters, the list and the target
• A loop that goes through the positions of the list
• Compares each item with the target and returns the position when equal
• Returns -1 after the loop, once every item has been checked

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

print(linear_search([4, 8, 15, 16], 15), linear_search([4, 8, 15, 16], 99))

3 Show the contents of the list after each of the first two passes of a bubble sort on the list [6, 2, 9, 4]. State whether a third pass is needed. 3

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

• After the first pass the list is [2, 6, 4, 9]
• After the second pass the list is [2, 4, 6, 9]
• A third pass is needed to confirm that no swaps are made

Model answer. First pass: 6 and 2 swap to give 2, 6, 9, 4. 6 and 9 are in order. 9 and 4 swap, so the list is [2, 6, 4, 9]. Second pass: 2 and 6 are in order, 6 and 4 swap, giving [2, 4, 6, 9]. Another pass is needed, because the second pass made a swap, and it will confirm there are no swaps so the algorithm can stop.

4 A programmer must find one name in an unsorted list of 20 names, once. Explain why a linear search is a better choice than sorting the list and then using a binary search. 3

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

• A binary search can only be used on a sorted list
• Sorting the list takes more steps than one linear search would
• The search is only done once so there is no benefit from sorting

Model answer. A binary search only works on a sorted list, so the names would have to be sorted first. Sorting 20 names takes more comparisons than simply checking all 20 once with a linear search. Because the search is only carried out once, there are no later searches to benefit from the sorted list, so the sorting would be wasted effort.

5 Compare a merge sort with a bubble sort for sorting a list of one million names. 4

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

• Merge sort needs far fewer comparisons on a large list
• Because it halves the list repeatedly, whereas a bubble sort compares neighbours over many passes
• Merge sort needs extra memory to hold the merged lists
• Bubble sort sorts in place and is simpler to write, but is too slow for a million items

Model answer. A merge sort is much better for a million names because it needs far fewer comparisons. It splits the list in half repeatedly and merges sorted halves, so the work grows slowly as the list grows, where a bubble sort makes many passes comparing neighbours and its work quadruples when the list is doubled. The cost of merge sort is that it needs extra memory for the lists it builds, whereas a bubble sort works in place and is simpler to write, but it would be far too slow for a million items.