Design algorithms in pseudocode, apply the standard searching and sorting algorithms, and compare algorithm efficiency.

What this dot point is asking

WJEC wants you to design algorithms and express them in pseudocode, to know the standard searching and sorting algorithms by heart, and to compare their efficiency. Algorithms are the core skill of computer science, and this dot point is heavily examined: you will be asked to trace an algorithm by hand, to spot which algorithm a fragment shows, and to justify why one is faster than another for a given size of data.

The answer

Designing an algorithm

Good algorithm design uses the three control structures (sequence, selection, iteration), validates its inputs, and is decomposed into manageable sub-problems. Designing first and coding second means errors are caught early, when they are cheap to fix.

Searching algorithms

A linear search examines each item in turn until the target is found or the list ends; it works on any list but is slow for large data. A binary search works only on a sorted list: it examines the middle item, then discards the half that cannot contain the target, repeating until found. Halving the list each step makes binary search dramatically faster on large data.

Sorting algorithms

WJEC expects you to trace these by hand on a short list, so practise showing the list after each pass or each insertion until the order is automatic.

Comparing efficiency

Efficiency is measured by how the number of operations grows as the input grows, captured by Big-O notation: linear search is O(n), binary search is O(log n), bubble and insertion sort are O(n squared), and merge sort is O(n log n).

Examples in context

Example 1. Looking up a name in a phone book

A phone book is sorted alphabetically, so you open it in the middle, see whether your name falls before or after, and discard half the book each time. This everyday action is a binary search, and it explains why the algorithm needs sorted data: the discard step depends on order.

Example 2. Why merge sort wins on big data

Sorting a million records with bubble sort takes on the order of a million squared operations, which is a trillion. Merge sort takes about a million times twenty, which is twenty million. The same task that is impractical with bubble sort finishes quickly with merge sort, showing why the growth rate, not the raw step count, decides scalability.

Example 3. Choosing the simple algorithm anyway

For a list of ten items, insertion sort's simplicity and low overhead can beat merge sort's recursion, even though merge sort wins asymptotically. Examiners reward recognising that Big-O describes large-n behaviour, and that for tiny inputs a simple algorithm may be the sensible choice.

Try this

Q1. State the worst-case Big-O time complexity of a linear search and of a binary search. [2 marks]

• Cue. Linear search is O(n); binary search is O(log n).

Q2. A bubble sort is applied to the list 3, 1, 2. State the list after the first complete pass. [2 marks]

• Cue. 1, 2, 3 (3 swaps past 1 and 2; the largest, 3, ends up last).