GCSE-ready- Home
- Lessons
- GCSE & IGCSE Computer Science
- Searching and sorting
Searching and sorting
🎬 The doodle video for this lesson is coming soon. Subscribe on YouTube to see it first.
Finding and ordering data quickly matters for every app you use. You need to know two searches and two sorts.
Linear and binary search
Linear search: check each item in turn from the start. Works on any list, but slow for big lists.
Binary search: the list must be sorted. Check the middle item; if it is not the target, throw away the half that cannot contain it. Repeat. Much faster on big lists.
Binary search: the list must be sorted. Check the middle item; if it is not the target, throw away the half that cannot contain it. Repeat. Much faster on big lists.
Bubble sort
Compare each pair of neighbouring items and swap them if they are in the wrong order.
One full pass moves the largest item to the end. Repeat passes until no swaps are needed.
[5, 1, 4, 2, 8] after one pass becomes [1, 4, 2, 5, 8].
One full pass moves the largest item to the end. Repeat passes until no swaps are needed.
[5, 1, 4, 2, 8] after one pass becomes [1, 4, 2, 5, 8].
Merge sort
Divide the list in half again and again until each list has one item.
Then merge pairs of lists back together in order.
Merge sort is usually much faster than bubble sort on large lists, but uses more memory.
Then merge pairs of lists back together in order.
Merge sort is usually much faster than bubble sort on large lists, but uses more memory.
Use binary search to find 23 in [3, 8, 12, 15, 23, 31, 40].
- Middle item is 15. 23 > 15, so discard the left half.
- Remaining: [23, 31, 40]. Middle item is 31. 23 < 31, so discard the right.
- Remaining: [23]. Found.
Answer: Found in 3 comparisons.
Linear search checks every item; binary search halves a sorted list each time. Bubble sort swaps neighbours in passes; merge sort splits then merges and is faster on big lists.
Check you have got it
Answer 6 quick questions with instant marking. If you get one wrong, GCSE-ready shows you why and gives you another go. It is free, and you do not need an account.