What you'll learn
An algorithm is a precise sequence of steps that solves a problem. In OCR GCSE Computer Science (J277, section 2.1) you need to understand the principles of computational thinking — abstraction, decomposition and algorithmic thinking — and be able to design, refine and represent algorithms using structure diagrams, flowcharts, pseudocode and OCR Exam Reference Language. You must also be able to identify and correct errors, use trace tables, and know the standard searching algorithms (linear and binary search) and sorting algorithms (bubble, merge and insertion sort). This guide explains each, with worked traces of the kind you will meet on Paper 2.
Algorithm questions reward precision. You may have to complete a trace table step by step, state which search is more efficient and why, or show the state of a list after each pass of a sort. Practise by working through examples by hand.
Key terms and definitions
Algorithm — A sequence of steps that can be followed to complete a task or solve a problem.
Computational thinking — Using techniques such as abstraction, decomposition and algorithmic thinking to solve problems.
Abstraction — Removing unnecessary detail to focus on the important parts of a problem.
Decomposition — Breaking a complex problem down into smaller, more manageable sub-problems.
Algorithmic thinking — Identifying the steps needed to solve a problem, in the right order.
Structure diagram — A diagram showing how a problem is broken down into sub-problems.
Flowchart — A diagram that represents an algorithm using standard symbols connected by arrows.
Pseudocode — A way of writing an algorithm using structured English-like statements, not tied to one programming language.
Trace table — A table used to record the values of variables as an algorithm is executed step by step.
Linear search — Checking each item in a list in turn until the target is found or the list ends.
Binary search — Repeatedly checking the middle item of a sorted list and discarding the half that cannot contain the target.
Bubble sort, merge sort, insertion sort — Algorithms that arrange items into order.
Core concepts
Computational thinking
Abstraction means focusing on what matters. A map of an underground railway shows stations and connections but ignores the real distances and street layout, because a traveller only needs to know the order of stations and where to change. When designing a program, abstraction means deciding which details to represent and which to ignore.
Decomposition means breaking a big problem into smaller parts that can be solved separately, often by different people, and then combined. A game might be decomposed into input handling, movement, scoring, graphics and saving.
Algorithmic thinking means working out the precise steps, in order, that solve each part, so that they could be followed by a computer.
Inputs, processes and outputs
Before designing an algorithm, identify:
- inputs — the data the algorithm needs;
- processes — what it does with the data;
- outputs — the results it produces.
For a program that calculates the average of test scores: inputs are the scores; processes are adding them and dividing by how many there are; the output is the average.
Representing algorithms
Structure diagrams show decomposition as a hierarchy: the main problem at the top, with sub-problems beneath.
Flowcharts use standard symbols:
- an oval (terminator) for start and end;
- a parallelogram for input and output;
- a rectangle for a process;
- a diamond for a decision, with Yes/No branches;
- a rectangle with double side lines for a sub-program.
Pseudocode and OCR Exam Reference Language describe algorithms in text. For example, a program that asks for a password until it is correct:
password = ""
while password != "Secret1"
password = input("Enter password")
endwhile
print("Access granted")
You can answer questions in pseudocode, OCR Exam Reference Language or a high-level language, as long as the logic is clear.
Errors and trace tables
Syntax errors break the rules of the language (such as a missing bracket) and stop the program running. Logic errors let the program run but produce the wrong result (such as using > instead of >=).
A trace table records each variable's value at each step. Example algorithm:
total = 0
for i = 1 to 4
total = total + i
next i
print(total)
| i | total | output |
|---|---|---|
| — | 0 | |
| 1 | 1 | |
| 2 | 3 | |
| 3 | 6 | |
| 4 | 10 | |
| 10 |
Trace tables help find logic errors and show you understand exactly what an algorithm does.
Linear search
Start at the first item and compare each item with the target in turn. Stop when it is found or when the end of the list is reached.
- Works on unsorted or sorted lists.
- Simple to code.
- Slow for large lists: in the worst case, every item must be checked.
Binary search
Binary search only works on a sorted list.
- Find the middle item (if there is an even number, OCR accepts either middle item, used consistently).
- If it is the target, stop.
- If the target is smaller, discard the middle item and everything after it; if larger, discard the middle item and everything before it.
- Repeat with the remaining half until the target is found or no items remain.
Each comparison halves the list, so binary search is much faster for large lists: a sorted list of 1,000 items needs at most about 10 comparisons, while a linear search might need 1,000. However, the list must be sorted first, and the algorithm is more complex.
Bubble sort
Compare each pair of adjacent items; if they are in the wrong order, swap them. One complete run through the list is a pass. After each pass, the largest remaining item has "bubbled" to its correct place at the end. Repeat passes until a pass makes no swaps.
- Simple to understand and code.
- Inefficient for large lists, because many comparisons and swaps are needed.
Insertion sort
Take the items one at a time, starting from the second, and insert each into its correct position within the already sorted part on its left, shifting larger items one place right.
- Simple, efficient for small or nearly sorted lists.
- Slow for large unsorted lists.
Merge sort
Merge sort uses divide and conquer:
- Split the list in half repeatedly until each sub-list contains one item (a list of one item is sorted).
- Merge pairs of sub-lists, comparing their first items and placing them in order, to produce sorted lists of two, then four, and so on, until one sorted list remains.
- Very efficient for large lists.
- More complex to code and uses more memory, because it creates new lists while merging.
Comparing the sorting algorithms
| Bubble sort | Insertion sort | Merge sort | |
|---|---|---|---|
| Method | Swap adjacent pairs; repeat passes | Insert each item into the sorted part | Split into single items, then merge |
| Efficiency on large lists | Poor | Poor | Good |
| Efficiency on nearly sorted lists | Can stop early if a pass has no swaps | Very good | Still splits and merges everything |
| Memory | Sorts in place | Sorts in place | Needs extra memory for new lists |
| Ease of coding | Easy | Easy | Harder |
The best algorithm depends on the situation: a small or nearly sorted list suits insertion sort; a very large list suits merge sort; bubble sort is mainly used to teach the idea of sorting.
Thinking about efficiency
Efficiency usually means how many steps (comparisons or swaps) an algorithm needs as the amount of data grows. Doubling a list's length roughly doubles the worst-case work for a linear search, but adds only one extra comparison for a binary search. That is why binary search is preferred for large sorted data, even though the data must first be sorted and the algorithm is harder to write.
Worked examples
Example 1: Binary search
Show the steps of a binary search for 23 in the sorted list: 3, 8, 12, 15, 23, 31, 42.
The middle item is 15 (position 4). 23 > 15, so discard 15 and everything before it: 23, 31, 42. The middle is 31. 23 < 31, so discard 31 and everything after it: 23. The middle is 23 — found, after three comparisons.
Example 2: Bubble sort, first pass
Show the first pass of a bubble sort on 5, 2, 9, 1.
Compare 5 and 2 → swap → 2, 5, 9, 1. Compare 5 and 9 → no swap. Compare 9 and 1 → swap → 2, 5, 1, 9. After the first pass: 2, 5, 1, 9. The largest item, 9, is now in place.
Example 3: Merge sort
Show how merge sort orders 6, 3, 8, 1.
Split: [6, 3] and [8, 1] → [6] [3] [8] [1]. Merge: [3, 6] and [1, 8]. Merge: compare 3 and 1 → 1; compare 3 and 8 → 3; compare 6 and 8 → 6; then 8. Result: 1, 3, 6, 8.
Example 4: Choosing a search
A list of 50,000 customer IDs is stored in order. Which search is most suitable? Explain. (2 marks)
Answer: Binary search (1), because the list is sorted and binary search halves the number of items to check each time, so it needs far fewer comparisons than a linear search (1).
Common mistakes and how to avoid them
- Using binary search on an unsorted list. It only works on sorted data.
- Forgetting to discard the middle item in binary search.
- Stopping a bubble sort too early. It finishes only when a pass makes no swaps.
- Confusing abstraction and decomposition. Abstraction removes detail; decomposition breaks a problem into parts.
- Skipping rows in trace tables. Record every change in the order it happens.
- Describing merge sort without the splitting stage.
Exam technique for "Algorithms"
- When describing an algorithm, use numbered steps or clear pseudocode.
- When asked to show a sort, write out the list after each step or pass as instructed.
- For comparisons of algorithms, refer to efficiency (number of comparisons), requirements (sorted data) and complexity/memory.
- In trace tables, work line by line and keep the columns aligned.
Quick revision summary
- Abstraction removes unnecessary detail; decomposition breaks problems into sub-problems; algorithmic thinking sets out the steps.
- Identify inputs, processes and outputs.
- Represent algorithms with structure diagrams, flowcharts and pseudocode/OCR Exam Reference Language.
- Trace tables record variable values to test algorithms and find logic errors.
- Linear search: any list, simple, slow on large lists. Binary search: sorted lists only, halves each time, fast.
- Bubble sort: swap adjacent pairs, passes until no swaps. Insertion sort: insert each item into the sorted part. Merge sort: split to single items then merge — efficient but uses more memory.