What is actually assessed
This sub-topic has an unusually precise set of demands, and one of them is a relief. You need to:
• Understand the main steps of each algorithm and the segments of code in it • Understand any pre-requisites of an algorithm • Apply the algorithm to a data set • Identify an algorithm if given the code, pseudocode or Exam Reference Language for it
You are not required to remember the code, pseudocode or Exam Reference Language for these algorithms. So the effort belongs in being able to run each one by hand on a list of numbers, and in recognising which algorithm a piece of given code is — not in memorising implementations.
The two searching algorithms
A linear search starts at the first item and checks each in turn until it finds what it is looking for or reaches the end of the list. It has no pre-requisite at all — the list may be in any order.
A binary search repeatedly halves the search space. It checks the middle item; if that is the target it stops; if the target is smaller it discards the whole upper half, and if larger it discards the lower half. It then repeats on what remains.
Binary search has a pre-requisite, and it is the detail most often examined: the list must already be sorted. Without an ordered list there is no way to know which half to discard, so the algorithm cannot work.
Worked example
Apply a binary search to find 23 in the list 4, 8, 15, 16, 23, 42, 50.
- The list is already in order, so the pre-requisite is met. There are 7 items, positions 1 to 7.
- The middle item is position 4, which holds 16. 23 is greater than 16, so discard 16 and everything before it.
- The remaining list is 23, 42, 50 — positions 5 to 7. The middle of these is position 6, holding 42.
- 23 is less than 42, so discard 42 and everything after it.
- The remaining list is just 23 at position 5. Check it: it matches.
Answer: 23 is found at position 5, after three comparisons — against 16, then 42, then 23 itself. A linear search would have taken five comparisons to reach it.
- Linear search
- a search that starts at the first item and checks each in turn until it finds the target or reaches the end; it has no pre-requisite, so the list may be in any order
- Binary search
- a search that repeatedly halves the search space by checking the middle item; it requires the list to be sorted first
The three sorting algorithms
Bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order, working from one end of the list to the other. That is one pass. It repeats passes until a complete pass happens with no swaps, which means the list is sorted. The name comes from the largest value 'bubbling' to the end on the first pass.
Insertion sort takes the items one at a time and inserts each into its correct place among the items already sorted, shuffling the larger ones along to make room. After processing n items, the first n items are in order. It is how most people sort a hand of playing cards.
Merge sort repeatedly splits the list in half until every part contains a single item — a list of one is necessarily sorted. It then merges pairs of lists back together, each time taking the smaller of the two front items, so that each merged list comes out in order. Splitting, then merging, is the pattern to remember.
Worked example
Show the first complete pass of a bubble sort on the list 5, 3, 8, 1.
- Compare the first pair, 5 and 3. 5 is larger, so swap them: 3, 5, 8, 1.
- Compare the next pair, 5 and 8. They are already in order, so no swap: 3, 5, 8, 1.
- Compare the next pair, 8 and 1. 8 is larger, so swap: 3, 5, 1, 8.
- The end of the list has been reached, so the pass is complete.
- Note what has been achieved: the largest value, 8, has reached its final position.
Answer: After the first pass the list is 3, 5, 1, 8, with two swaps made. The largest item is now in its final place, so the next pass need only consider the first three items. Further passes give 3, 1, 5, 8 and then 1, 3, 5, 8, after which a pass with no swaps confirms the list is sorted.
Common mistake
Do not describe a bubble sort as complete after one pass. One pass places only the largest item; the algorithm finishes when a whole pass is made without a single swap.
- Bubble sort
- a sort that compares each pair of adjacent items and swaps them if they are in the wrong order, repeating passes until a complete pass happens with no swaps
- Merge sort
- a sort that repeatedly splits the list in half until each part holds one item, then merges the parts back together in order
- Insertion sort
- a sort that takes each item in turn and inserts it into its correct position among the items already sorted
Before you practise
- You do not have to remember the code for these algorithms — you have to run them and recognise them.
- Linear search checks each item in turn and needs no pre-requisite.
- Binary search checks the middle item and discards half the list, but requires a sorted list.
- Bubble sort swaps adjacent pairs across repeated passes, finishing when a pass makes no swaps.
- Insertion sort inserts each item into its correct position among those already sorted.
- Merge sort splits the list down to single items, then merges pairs back together in order.
- Bubble sort is simple but slow; insertion sort suits small or nearly sorted lists; merge sort is fastest on large lists but uses more memory.
- When applying an algorithm to a data set, show every comparison or pass — the working carries the marks.