Algorithms
Watch sorting and searching algorithms execute step-by-step with a live trace table. Covers bubble sort, insertion sort, linear search and binary search for GCSE, plus Dijkstra's algorithm and A* pathfinding for A Level Computer Science. Every step shows exactly what changes — just like an exam trace question.
Step 1/62 Bubble sort: scan left→right, swap adjacent pairs if out of order. Largest "bubbles" to the end each pass.
| Pass | j | a[j] | a[j+1] | Action |
|---|---|---|---|---|
| Press Play or Step → to see trace | ||||
Big O notation is assessed at A Level (AQA 7517, OCR H446) — not required at GCSE. GCSE students should focus on tracing algorithms by hand and comparing the number of comparisons made.
| Algorithm | Level | Best case | Worst case | Space |
|---|---|---|---|---|
| Bubble Sort | GCSE | O(n) | O(n²) | O(1) |
| Insertion Sort | GCSE | O(n) | O(n²) | O(1) |
| Linear Search | GCSE | O(1) | O(n) | O(1) |
| Binary Search | GCSE | O(1) | O(log n) | O(1) |
| Dijkstra's | A Level | O((V+E)log V) | O((V+E)log V) | O(V) |
| A* Search | A Level | O(E) | O(b^d) | O(V) |
A Level exam tip: Dijkstra guarantees the shortest path in a non-negative weighted graph but explores in all directions. A* uses a heuristic h(n) to focus the search toward the goal — it finds the same optimal path but typically visits far fewer nodes. A* is only optimal when h(n) is admissible (never overestimates the true cost). V = vertices, E = edges, b = branching factor, d = depth.
Each algorithm below is assessed at either GCSE or A Level. Click the algorithm in the visualiser above to see it in action with a live trace table.
Repeatedly scans the array comparing adjacent pairs and swapping them if they are in the wrong order. After each complete pass, the largest unsorted element "bubbles" to its correct position at the end. The algorithm can terminate early if a complete pass produces no swaps — this is an important efficiency feature to mention in the exam.
Builds a sorted section one element at a time, starting from the left. Takes each new element from the unsorted part and inserts it into the correct position in the sorted section by shifting larger elements one place to the right.
Checks each element from the start of the list in order until the target is found or the list is exhausted. Works on both sorted and unsorted data. Simple to implement but can require checking every element in the worst case.
Requires a sorted list. Finds the midpoint of the current search range, compares it to the target, then discards the half that cannot contain the target and repeats. For 1,024 elements at most 10 comparisons are needed — far fewer than checking every element.
O((V+E) log V) Finds the shortest path in a weighted graph from a source node to all other nodes. Uses a priority queue (ordered by distance) to always expand the nearest unvisited node first. Guarantees the optimal shortest path for graphs with non-negative edge weights.
O(b^d) worst case An informed extension of Dijkstra that uses a heuristic h(n) — an estimate of the remaining cost to reach the goal. Combines actual cost from the start g(n) with the heuristic estimate: f(n) = g(n) + h(n). Always expands the node with the lowest f score. Finds the optimal path if h(n) is admissible (never overestimates).
GCSE vs A Level: At GCSE you need to trace algorithms by hand and describe how they work — you do not need Big O notation. Big O time and space complexity is A Level only (AQA 7517, OCR H446). For GCSE, focus on being able to write out each step and compare algorithms based on number of comparisons for a given input.
At GCSE (AQA 8525, OCR J277, Cambridge 0478) you need to know bubble sort and insertion sort — how they work step by step and how to trace through them by hand. You should be able to write out the state of the array after each pass of bubble sort, and show each insertion for insertion sort. Big O time complexity is not required at GCSE; it is A Level content.
No. Big O notation (O(n), O(n²), O(log n)) is assessed at A Level only — AQA 7517 and OCR H446. At GCSE you need to be able to trace algorithms by hand and compare them based on the number of comparisons made. For example, a GCSE question might ask: "How many comparisons does a binary search make on a list of 16 items?" — you work this out from the algorithm, not from Big O.
Linear search checks each element in order from the first — it works on any list (sorted or unsorted) but can require checking every element in the worst case. Binary search repeatedly halves the search space and is much faster, but the list must already be sorted. For a list of 1,024 items, binary search takes at most 10 comparisons rather than up to 1,024 for linear search.
Both are A Level algorithms for finding the shortest path through a weighted graph. Dijkstra's algorithm explores nodes in order of their distance from the start. A* improves on this by using a heuristic — an estimate of remaining distance — to focus the search towards the goal. Both are assessed at A Level (AQA 7517 and OCR H446). They are not required at GCSE.
Write out the full array. On each pass, compare adjacent pairs from left to right — if the left value is greater than the right, swap them. Write out the array after each complete pass. If a full pass makes no swaps, the array is sorted and you can stop — always note this early termination in your answer.