Searching and sorting
Computer Science · GCSE · The School
Two ways to find
LINEAR search checks items one by one from the start — works on any list, slow on big ones (up to n checks for n items). BINARY search needs a SORTED list: check the middle, discard the half that cannot contain the target, repeat. Each step halves the problem — a million items need at most ~20 checks. Sorted-ness is the price of that speed.
Bubble sort, honestly slow
Bubble sort walks the list comparing neighbours and swapping when out of order; each full pass "bubbles" the largest remaining value to the end. [5,3,8,2]: pass 1 → [3,5,2,8]; pass 2 → [3,2,5,8]; pass 3 → [2,3,5,8]. Easy to write and trace, painful at scale — its comparisons grow with n², so doubling the list quadruples the work.
Why efficiency matters
For 10 items, nothing matters. For 10 million — a search engine, a game leaderboard — the difference between n and log(n), or n² and n·log(n), is the difference between instant and unusable. GCSE asks you to compare algorithms in exactly these terms: how does the work grow as the input grows?
Start: 5, 3, 8, 1. Compare 5 and 3 — swap: 3, 5, 8, 1. Compare 5 and 8 — no swap. Compare 8 and 1 — swap: 3, 5, 1, 8. End of pass one, and the largest value has bubbled to the end, which is guaranteed after every pass. Pass two: 3, 5, 1, 8 → 3, 1, 5, 8. Pass three: 1, 3, 5, 8. Sorted. Note that the number of comparisons grows with the SQUARE of the list length — which is why it is not used on real data.