AlgorithmLab

Explore an algorithm: predict, step, inspect the code, then modify the data.

Investigating
Comparisons 0Array writes 0Swaps 0
Indices start at 0 · ascending order

Compare neighbours. Swap when the left value is larger.

A · Bubble sort
1PROCEDURE bubble_sort(a)
2 FOR end = length(a) − 1 DOWNTO 1
3 swapped = FALSE
4 FOR j = 0 TO end − 1
5 IF a[j] > a[j + 1] THEN
6 SWAP a[j], a[j + 1]
7 swapped = TRUE
8 IF swapped = FALSE THEN
9 EXIT LOOP
10 RETURN a

Highlighted statement for this teaching event. Pseudocode is explanatory, not a claim of exact OCR Exam Reference Language syntax.

◆ Active✓ Ordered region× DiscardedRelative bar heights · numeric labels are authoritative

AlgorithmLab learning guide

Predict → Run → Investigate → Modify → Make. Explore searches and sorts with indexed data, reversible snapshots and statements highlighted in Python or explanatory pseudocode. Indices start at 0. These are teaching-event traces, rather than a live Python debugger: loop bookkeeping can occur between events. The Python procedures show the implemented variants.

Six algorithms

Linear search: Works on unsorted data. This version returns the first matching index; −1 means not found.

Binary search: Requires ascending sorted data. Uses the lower middle index when there are two middle items. A duplicate match need not be the first occurrence.

Bubble sort: An ascending, stable version with a shrinking end boundary and early exit after a pass with no swaps.

Insertion sort: Builds a sorted prefix. Equal values are not shifted past each other, so this version is stable. A held key lives outside the main array during shifts.

Merge sort: Top-down, stable merge sort. Temporary L/R buffers preserve values while the main array is overwritten. Recursion uses an additional O(log n) call stack.

Quick sort: This is last-item-pivot Lomuto partitioning with ≤ comparisons. Self-swaps are skipped. It is not stable. Sorted, reversed or all-equal input can produce unbalanced partitions and quadratic work.

Compare fairly

Compare two searches or two sorts on identical data. Each lane advances one teaching event per click; event counts and animation finish times are not execution-time measurements. Compare the operation counters instead. Search preparation (sorting for binary search) is explicit and outside the search counters.

Counters and colours

Comparisons count data-value tests, excluding loop/bounds tests. Binary search counts equality and less-than separately. Array writes count writes to the main array only; a real swap writes two cells. Self-swaps are skipped. Peak extra values counts the held insertion key or merge buffers, separately from recursive call depth. Big O describes asymptotic growth, not exact timing.

Active cells are marked with a diamond; ordered regions with a tick; discarded search candidates with a cross. Ordered prefixes or merged ranges can change in later stages. The pivot is labelled P. Insertion shifts and merge writes can temporarily duplicate array values; the held key and L/R buffers preserve the unread data. Bar heights show relative values, including negative numbers; use numeric labels, not height alone.

Advanced view

Advanced adds last-pivot quick sort, variable inspection, recursive call stacks and efficiency summaries. Merge sort also exposes its recursive stack here. Switching views keeps your data; returning to GCSE replaces an advanced-only quick-sort selection with a GCSE algorithm.

Challenges and saving

All 18 activities are independent. Check a prediction, investigate with Step/Back, then choose indexed cells or enter an answer. The trace stops before the checked result. Correct actions reveal their verified snapshot, and Modify in Explore lets you change the example. Optional hints and check counts are recorded on this browser/device. Shared computers share these records. No student login, XP, cloud saves or class-dashboard records are used. Custom Explore data is kept only while this page stays open.

Worked challenge answers

01 · Start the search: It can check items sequentially in any order. Array indices begin at 0. Linear search starts at the beginning.

02 · Nothing to find: −1 is the agreed not-found result. Index 0 is a valid match and cannot mean missing. The array contains no 5. A missing target returns −1.

03 · The first duplicate: The return statement exits the procedure immediately. The first 4 is at index 0.

04 · Find the middle: Sorted order is what allows an entire half to be safely discarded. floor((0 + 7) / 2) is 3.

05 · Discard half: The target can only be beyond the middle in this ascending array. The first middle index is 3. Keep indices 4 through 7.

06 · An empty range: −1 is the agreed not-found result. Index 0 is a valid match and cannot mean missing. 7 falls between existing values. low eventually becomes greater than high.

07 · Neighbours first: It compares adjacent cells and swaps values that are out of ascending order. Select indices 0 and 1.

08 · Make the swap: The larger left value must move right. The first pair is 7 and 2 at indices 0 and 1.

09 · One full pass: Repeated neighbour comparisons move the maximum to the last active position. 7 moves right each time. The result is 2, 5, 1, 7.

10 · Hold a key: Array cells may be overwritten while the key waits outside the main array. The first element is a one-item sorted prefix. The first key comes from index 1.

11 · Shift right: The larger value moves right to make room for the held key. 9 is copied from index 0 to index 1.

12 · Fill the gap: The prefix is sorted so far; later keys can still move its values. The held key is 3. It fills index 0.

13 · Divide the range: A zero- or one-item range needs no sorting. Indices 0–3 split at mid=1. The left half spans 0–1.

14 · Read the buffers: The main array changes during merging; the buffers keep the sorted halves available. The first two one-item buffers contain 8 and 3. Take 3 first.

15 · Merge to the finish: It repeatedly selects the next smallest item from sorted buffers. Both 3s stay in the result: 2, 3, 3, 6, 8.

16 · Choose the pivot: The displayed Lomuto variant uses a[high]. Other correct quick-sort variants make different choices. 6 is the last value, at index 4.

17 · Fix the pivot: This variant moves values less than or equal to the pivot into the lower partition. Three values (4, 2 and 1) go before 6. Its index is 3.

18 · An unbalanced split: The pivot is always the maximum, giving sizes n−1 and 0 rather than balanced halves. Count 5 + 4 + 3 + 2 + 1 = 15 comparisons.

Curriculum references

OCR GCSE J277 §2.1.3 · OCR A-level H446 §2.3.1. This lab supports these topics; it is not complete coverage of either specification.

Back to Primm Tools