What you'll learn
An algorithm is a set of step-by-step instructions for solving a problem, and algorithms are at the heart of all computer programs. For AQA GCSE Computer Science you need to understand what an algorithm is, how to represent algorithms using pseudocode and flowcharts, the main searching and sorting algorithms, and how to compare and trace them. This guide covers algorithms and their representation, searching algorithms, sorting algorithms, and how to evaluate them. By the end you should be able to describe, trace and compare the standard algorithms on the specification.
Key terms and definitions
Algorithm — A set of step-by-step instructions to solve a problem or complete a task.
Decomposition — Breaking a problem down into smaller, more manageable parts.
Abstraction — Removing unnecessary detail to focus on the important features of a problem.
Pseudocode — A way of writing an algorithm in structured, English-like statements.
Flowchart — A diagram that represents an algorithm using standard symbols.
Linear search — Checking each item in a list in turn until the target is found.
Binary search — Repeatedly halving a sorted list to find the target.
Bubble sort — A sorting algorithm that repeatedly swaps adjacent items that are in the wrong order.
Core concepts
What an algorithm is
An algorithm is a set of step-by-step instructions for solving a problem or completing a task. Algorithms must be clear, unambiguous and finite (they must end). The same problem can often be solved by different algorithms, some more efficient than others. Two key techniques help in designing algorithms: decomposition (breaking a problem into smaller parts) and abstraction (ignoring unnecessary detail to focus on what matters).
Representing algorithms
Algorithms can be represented in two main ways at GCSE:
- Pseudocode — a way of writing the steps using structured, English-like statements that are close to program code but not a specific language. It uses constructs like IF, WHILE and FOR.
- Flowcharts — diagrams using standard symbols: a rounded box for start/stop (terminal), a rectangle for a process, a parallelogram for input/output, and a diamond for a decision. Arrows show the flow.
Being able to read and write algorithms in both forms, and to convert between them, is a common exam requirement.
Linear search
Linear search is the simplest search algorithm. It checks each item in the list in turn, from the start, until it finds the target or reaches the end. Its advantages are that it is simple and works on any list, whether sorted or not. Its disadvantage is that it can be slow, because for a long list it may have to check every item.
Binary search
Binary search is a faster search, but it only works on a sorted list. It works by repeatedly halving the list:
- Look at the middle item of the list.
- If it is the target, stop.
- If the target is smaller, repeat with the lower half; if larger, repeat with the upper half.
- Continue halving until the target is found or no items remain.
Because it halves the search area each time, binary search is much faster than linear search for large lists — but the list must be sorted first.
Comparing the two searches
The key comparison is: linear search works on any list but is slower; binary search is much faster for large lists but requires the list to be sorted. For a small or unsorted list, linear search may be the better choice; for a large sorted list, binary search is far more efficient.
Bubble sort
Bubble sort puts a list into order by repeatedly comparing adjacent items and swapping them if they are in the wrong order:
- Go through the list, comparing each pair of adjacent items.
- Swap them if they are in the wrong order.
- Repeat these passes through the list until no swaps are needed (the list is sorted).
Each pass "bubbles" the largest remaining item to its correct place. Bubble sort is simple to understand but can be slow for large lists, because it may need many passes and comparisons.
Merge sort
Merge sort is a more efficient sorting algorithm that uses decomposition. It works by:
- Splitting the list repeatedly into halves until each part has just one item.
- Merging the parts back together in the correct order.
Merge sort is generally faster than bubble sort for large lists, but it is more complex and uses more memory. Comparing bubble sort (simple but slow) with merge sort (faster but more complex) is a common exam point.
Decomposition and abstraction in problem solving
Two computational-thinking techniques underpin algorithm design and are commonly tested. Decomposition means breaking a large, complex problem into smaller sub-problems that are easier to solve one at a time — for example, splitting "write a game" into handling input, updating the game state, and drawing the screen. Abstraction means removing unnecessary detail so you can focus on the important parts of a problem — for example, representing a map as a simple grid rather than including every real-world feature. Together, these techniques make problems manageable and are the reason algorithms like merge sort (which decomposes a list into halves) work so effectively. Being able to define both, and give an example of each, is a frequent exam requirement.
Efficiency and choosing the right algorithm
A key idea in this topic is that different algorithms solving the same problem can have very different efficiency, and choosing the right one matters. Efficiency usually refers to how the time (or number of steps) grows as the amount of data increases. For searching, binary search is far more efficient than linear search on a large sorted list, because it halves the data each step instead of checking every item. For sorting, merge sort is more efficient than bubble sort for large lists. But efficiency is not the only consideration — binary search requires the data to be sorted first, and merge sort is more complex and uses more memory. Choosing an algorithm therefore means balancing speed against requirements and complexity, which is exactly the kind of judgement exam questions ask you to explain.
Worked examples
Example 1: When to use binary search
Why can binary search not be used on an unsorted list? Binary search works by comparing the target with the middle item and discarding half the list based on whether the target is larger or smaller. This only works if the list is sorted; on an unsorted list, you cannot rule out half the items, so binary search would not work.
Example 2: Tracing a linear search
Using linear search, how many items are checked to find the value 7 in the list [3, 5, 7, 9]? Linear search checks each item from the start: 3 (no), 5 (no), 7 (found). So 3 items are checked before the target is found.
Example 3: A bubble sort pass
In one pass of bubble sort on [5, 3, 4], what happens? Compare 5 and 3: they are in the wrong order, so swap to get [3, 5, 4]. Compare 5 and 4: wrong order, swap to get [3, 4, 5]. After this pass the list is sorted, and another pass with no swaps confirms it.
Example 4: Comparing sorts
Give one advantage of merge sort over bubble sort. Merge sort is generally much faster than bubble sort for large lists, because it splits the list and merges the parts efficiently, rather than repeatedly passing through the whole list as bubble sort does.
Common mistakes and how to avoid them
A common error is trying to use binary search on an unsorted list. Binary search requires a sorted list; if the list is not sorted, linear search must be used instead.
Students often confuse the searches. Linear checks each item in turn (any list, slower); binary halves a sorted list (much faster). Remember binary needs sorting.
Another mistake is describing bubble sort incorrectly. It compares and swaps adjacent items, repeating passes until no swaps are needed. Leaving out the repeated passes is a common error.
When tracing algorithms, work through them carefully step by step and write down the list after each stage. Rushing leads to mistakes in the trace.
Finally, when comparing algorithms, mention both speed and requirements/complexity — for example, binary search is faster but needs a sorted list; merge sort is faster than bubble sort but more complex.
Exam technique for "Fundamentals of Algorithms"
Be ready to read and write algorithms in pseudocode and flowcharts, using the correct flowchart symbols. Converting between the two is commonly tested.
Know the standard algorithms — linear search, binary search, bubble sort and merge sort — and be able to trace them step by step on a given list, showing your working after each stage.
For comparison questions, state the trade-offs: linear vs binary search (any list but slower vs sorted but faster), and bubble vs merge sort (simple but slow vs faster but more complex). Use precise terms — algorithm, decomposition, abstraction, linear/binary search, bubble/merge sort — throughout.
Quick revision summary
- An algorithm is a set of step-by-step instructions; decomposition (break into parts) and abstraction (remove detail) help design them.
- Represent algorithms with pseudocode or flowcharts (terminal, process, input/output, decision symbols).
- Linear search: checks each item in turn; works on any list but is slower.
- Binary search: halves a sorted list each time; much faster but requires sorting.
- Bubble sort: repeatedly swaps adjacent items until no swaps are needed; simple but slow.
- Merge sort: splits the list and merges in order; faster than bubble sort for large lists but more complex.