Retrieval: Searching and Sorting Algorithms

Retrieval — Year 12's searching and sorting algorithms

Retrieval: this lesson is a deliberate consolidation before the sequence's genuinely new material. Year 12 Sequence 5 covered four algorithms and how to analyse their performance — all four are retrieved here, precisely, before this sequence builds algorithms that go well beyond them.

Key vocabulary

Best / worst / average case — how an algorithm performs depending on the specific input, not just its size.
Comparison — a single "is this bigger/smaller/equal" check, the basic unit most of these algorithms' complexity is measured in.

Understand — the four algorithms, precisely retrieved

Algorithm	What it does	Complexity	Requires sorted data?
Linear Search	Checks each element in turn until found or exhausted	O(n) worst case	No
Binary Search	Repeatedly halves a sorted array by comparing to the middle element	O(log n) worst case	Yes
Bubble Sort	Repeatedly swaps adjacent out-of-order pairs until no swaps are needed	O(n²) worst case	No
Insertion Sort	Builds a sorted section one element at a time, inserting each into its correct position	O(n²) worst case, but efficient on nearly-sorted data	No

See it — why each complexity follows from its structure (retrieved reasoning, re-applied)

Linear search's O(n) follows directly from potentially having to check every single element once. Binary search's O(log n) follows from halving the remaining search space at every comparison — the number of times n can be halved before reaching 1 is log₂(n). Bubble sort's O(n²) follows from needing, in the worst case, roughly n passes, each potentially comparing up to n elements. Insertion sort shares bubble sort's O(n²) worst case, but degrades gracefully to close to O(n) when the data is already nearly sorted, since far fewer shifts are needed.

Analyse — applying this comparatively

For 1,000 elements: linear search may need up to 1,000 comparisons; binary search needs at most about 10 (log₂(1000) ≈ 10); bubble/insertion sort may need up to roughly 1,000,000 comparisons in the worst case. This gap is exactly why this sequence's new algorithms (which extend these same ideas to graphs, trees and weighted networks) matter so much at real-world scale.

Common mistake

Assuming binary search is simply "the better algorithm" and should always replace linear search. Binary search's O(log n) speed comes at a genuine cost: the data must already be sorted, and keeping it sorted after insertions has its own cost. For data that changes constantly, or is searched only once, linear search can genuinely be the more appropriate choice.

Check your understanding

A shop's till system searches a list of 40 barcodes for a match on every scan, and the list is rebuilt from scratch (in an arbitrary order) every morning. Identify which of the four algorithms above would be most appropriate, and justify your answer. (3 marks)

(Linear search. With only 40 items, the difference between O(n) and O(log n) is negligible in practice, and since the list is rebuilt in arbitrary order every day, keeping it sorted purely to enable binary search would add cost for no meaningful benefit at this small scale.)

Challenge

A teacher has a class list of 30 names that rarely changes across a term, and needs to look a name up frequently during registration. Propose which algorithm (and any necessary preparation) would be most appropriate, and justify your choice.

Looking ahead: this sequence introduces algorithms — graph traversal, merge sort, shortest-path finding — where tracing how an algorithm behaves is no longer enough on its own; you'll also need to reason about why each one is guaranteed to produce a correct result at all.