Algorithms and programming · GCSE Computer Science
Algorithms
Decomposition, abstraction, searching, sorting, and how to prove an algorithm works with a trace table.
Binary search only works if the list is already sorted.
The important bits
What you need to know
- 1
An algorithm is a precise sequence of steps that solves a problem in finite time. Computational thinking splits that craft into decomposition (break it up), abstraction (ignore the irrelevant), pattern recognition and algorithm design.
- 2
Represent algorithms as structured English, flowcharts, or the exam board’s pseudocode. Flowcharts: ovals start/stop, parallelograms input/output, rectangles process, diamonds decisions.
- 3
Linear search checks each item in order. It works on unsorted data. Worst case is n comparisons for n items — slow on a phone book, fine on a short list.
- 4
Binary search repeatedly halves a sorted list: compare the midpoint, discard the half that cannot contain the target. If the list is unsorted, binary search is wrong, not just slow.
- 5
Bubble sort compares neighbours and swaps until a pass makes no swaps. Easy to hand-trace; inefficient on large n. Merge sort splits to one-item lists then merges in order — more comparisons of a smarter kind, extra memory for the merge.
- 6
Insertion sort builds a sorted left-hand side by inserting each next item into its place. Good enough for small or nearly-sorted data; still a standard trace-table guest.
- 7
Efficiency at GCSE is mostly: time (how comparisons grow with n) and space (extra arrays). You may meet Big O names (linear O(n), binary search O(log n), bubble O(n²)); only use them if your board does.
- 8
Trace tables have a column per variable (and sometimes per output). Execute one line at a time. Most algorithm marks are lost by skipping a swap or updating the index twice in your head.
Go deeper
Why binary search feels like cheating until it fails
Looking up “Patel” in a sorted register, you do not start at A. You open the middle, discard half, and repeat. That is binary search: each question gives one bit of information and halves the remaining search space, so 1,000 items need about ten checks, not a thousand. The hidden contract is order. If the register is shuffled, the middle tells you nothing about where Patel lives, and the algorithm can skip the name entirely. In an exam, state the precondition (sorted), show the mid index integer division, and be careful when the item is absent — you must stop when the sublist is empty, not loop forever. That termination condition is as important as the comparison.
Go deeper
Bubble versus merge, without mythology
Bubble sort is taught because you can see it. Adjacent compares, swap if out of order, a flag or a shrinking unsorted tail, repeat. On reverse-sorted data it does a lot of pointless work; on nearly sorted data a flag can exit early. Merge sort is divide-and-conquer: split until lists of length one (which are sorted), then merge two sorted lists by always taking the smaller head. It is consistently faster on large n and needs extra space for the merged copy. If a 6-mark question asks you to compare, use time, space, and whether the data is likely already sorted — not “merge is better because it is more advanced”.
See the idea in action
Trace binary search for 17 in [3, 8, 12, 17, 21, 30]. Low = 0, high = 5. Mid = 2, value 12, 17 > 12 so low = 3. Mid = 4, value 21, 17 < 21 so high = 3. Mid = 3, value 17, found. Count the comparisons (three) and note that linear search might have taken four. Then write the one-line warning: if the array had been [17, 3, 8, …] this method could miss 17.
Exam technique
Turn knowledge into marks
When the paper prints an algorithm, freeze it: tick each line, fill the trace table, only then answer “what is the output”. Reading it like a novel is how you drop marks on an off-by-one.
Common mistakes
Do not give these marks away
- 01
Running binary search on unsorted data.
- 02
Forgetting that bubble sort needs another pass after a swap — or forgetting the early-exit flag if the question includes one.
- 03
Writing “the algorithm is faster” with no reference to n, comparisons, or memory.
What must be true before you can correctly use binary search?
AThe list must contain only even numbers
BThe list must already be sorted
CThe list must be stored on paper, not in RAM
DThe list must have an odd length
Show the answer
The list must already be sorted. Binary search discards half the list based on a midpoint comparison. That decision is only valid if order is guaranteed. Unsorted data needs linear search (or a sort first).
Quick questions
If this is the bit you searched
Is a flowchart an algorithm?
It is a representation of one. The algorithm is the logical sequence; flowchart, pseudocode and Python are different clothes on the same instructions.
Which sort should I learn to trace?
Bubble sort first, because papers love it. Then insertion or merge if your specification names them. Being able to complete a trace table is worth more than naming five sorts you cannot execute.