The standard algorithms for computer science exams
8 min readUpdated
Most school computer science courses (GCSE, IGCSE, National 5, Higher, A level and AP) expect you to know a small set of standard algorithms: how they work, how to trace them and how they compare. Here they are in one place, in Python.
Linear search
Check each item in turn until you find the target. Works on any list, sorted or not. O(n).
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i
return -1Binary search
Only for a sorted list. Compare the middle item, then keep the half that can hold the target. O(log n).
def binary_search(items, target):
low, high = 0, len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
if items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1Bubble sort
Go through the list swapping neighbours that are in the wrong order; repeat until a pass makes no swaps. Simple but slow: O(n²).
def bubble_sort(items):
n = len(items)
swapped = True
while swapped:
swapped = False
for i in range(n - 1):
if items[i] > items[i + 1]:
items[i], items[i + 1] = items[i + 1], items[i]
swapped = True
n -= 1Insertion sort
Build a sorted part one item at a time, inserting each new item into its place. O(n²), but fast on lists that are nearly sorted.
Merge sort
Split the list in half, sort each half, then merge the two sorted halves. O(n log n), but it needs extra memory for the merge.
Which one to use
| Algorithm | Needs sorted data? | Time | Good for |
|---|---|---|---|
| Linear search | No | O(n) | Small or unsorted lists |
| Binary search | Yes | O(log n) | Large sorted lists |
| Bubble sort | No | O(n²) | Teaching; tiny lists |
| Insertion sort | No | O(n²) | Small or nearly sorted lists |
| Merge sort | No | O(n log n) | Large lists |
Frequently asked questions
Why does binary search need a sorted list?
It decides which half to keep by comparing with the middle item. That only works if smaller items are on one side and larger items on the other.
Which sort is fastest?
For large lists, merge sort (O(n log n)) is much faster than bubble or insertion sort (O(n²)). For a few items, the difference is tiny.
How do I trace a sort in the exam?
Write the list after every pass (or every swap, if asked), and check the order of the items each time.
Learn it step by step
Practise this, step by step
Short lessons with quizzes, practice and interview questions, from your first program to job-ready.