Search Party

Five algorithms, and none to memorise

Two things about this topic are unusual on this specification, and both of them change how you should spend your revision time. ⚠️ First: there are THREE sorting algorithms here, not two. Bubble, merge and insertion. Two of the other big exam boards require only bubble and merge, which means a great deal of revision material simply does not mention insertion sort at all. If yours does not, you are missing an examinable algorithm rather than an optional extra. ⚠️ Second, and it cuts the other way: this paper does not ask you to remember the code. The specification says so directly. You are asked to understand what each algorithm does, to recognise one from code you are shown, and to say when it is the right choice. So: more algorithms, less memorisation. Put the effort into tracing and explaining, which is the skill you built on the previous topic, and not into learning five algorithms by heart.

The five, in one place

Two searches and three sorts. Each one is given as an idea, because an idea is what the questions ask for.

Two searches, and the catch

Binary search is faster, and that is not the whole story. The third column is where the marks actually are.

What this paper asks you to do

Worth being precise about, because it is not what most people assume and it saves real time. You are not being asked to write an algorithm out from memory. You are being asked three things: say what one does, recognise one from code you are shown, and say when it is the right choice. ⚠️ So when a question puts unfamiliar code in front of you, look for the shape rather than the syntax. How does it move through the data - straight along, or splitting it, or going back over it repeatedly? What does it do at each step? The shape identifies it, and you already know how to work out what code does, because that is what tracing is for. ⚠️ And when a question asks which one to use, answer with a condition and not a preference. Not which is faster in general, but what has to be true of this data for each option to work at all. That sentence is usually the mark.

Match each algorithm to how it moves

The list is not sorted

You need to find one particular value in a list of 500 items that is NOT in any order, and you will only ever search it this once. What is the sensible choice?

• Use a linear search, since sorting the list first would cost more work than a single search saves
• Sort it first and then binary search it, since binary search is always the faster option
• Binary search it anyway, since the method works on any list
• Neither will work, because you cannot search an unsorted list

The sort nobody taught you

This is the third sort, and there is a good chance you have never met it, because the other big boards require only two. On this paper it is examinable exactly like the other two. ⚠️ It is also the one you already do without thinking about it, because it is how people sort a hand of cards. Go through the list one item at a time, from left to right. Everything to the left of the item you are holding is already in order. Take the item and move it back through that ordered part until it sits in the right place. Then pick up the next one and do the same. Worked on the list 5, 2, 4. Start with 5 on its own, which is trivially in order. Pick up the 2: it belongs before the 5, so the list becomes 2, 5, 4. Pick up the 4: it belongs between the 2 and the 5, so the list becomes 2, 4, 5. Every item has been placed, and the list is sorted. ⚠️ Worth knowing for a comparison question: it does very little work on a list that is already nearly in order, because each item is picked up, found to be in roughly the right place already, and put straight back down.

Sort the hand, one card at a time

Insertion sort the list 5, 2, 4. The dimmed part is not placed yet; the highlighted item is the one in your hand.

True about the three sorts

Select the TWO statements that are true.

• Insertion sort does very little work on a list that is already nearly in order
• Merge sort breaks the list down before building it back up in order
• Bubble sort finds the value you are searching for
• This specification requires you to write out the code for each algorithm from memory

Complete the searching and sorting paragraph

A search that checks each item in turn until it finds the target is a _____. A search that repeatedly examines the middle and discards half of what is left is a _____, and it only works if the data is already _____. A sort that repeatedly compares neighbouring items and swaps them is a _____. A sort that grows an ordered run at the front of the list, placing each new item where it belongs, is an _____.

Name the algorithm

Five behaviours, three lives. This is the skill the paper asks for: recognise it from what it does.

What is left after one look

A binary search begins on a sorted list of 64 items. It checks the middle and discards the half that cannot contain the target. Work out how many items are still left to be searched.

Spot the true searching and sorting facts

Tap the TWO statements that are true.

• Binary search only works if the data is already sorted
• This specification lists three sorting algorithms rather than two
• This specification requires the code for each algorithm to be recalled from memory
• Insertion sort is the same algorithm as bubble sort under a different name

Three algorithm calls

Three situations. Choose the response you could defend in writing.

• A classmate shows you revision notes covering bubble sort and merge sort, and says that is all the sorting there is. What do you tell them?
• A question shows you code for an algorithm you have never memorised, and asks what it does. How should you approach it?
• A list of names is kept permanently in alphabetical order and is searched many times every day. Which search, and why?

Explain the five, and what this paper wants

A friend has been revising searching and sorting from material written for a different exam board. Write them the answer that fills the gap and corrects their revision plan.

• Name the two searches and say how each one moves through the data
• Explain the condition binary search needs, and what you have to do if it is not met
• Name the three sorts this specification requires and give the key idea of each one
• Explain what insertion sort does, and why it is worth learning even though other revision material leaves it out
• Finish by explaining what this specification asks you to do with an algorithm's code, and what it does not ask for