Linear search
- Check each item in turn, starting at the beginning, until you find the target or reach the end of the list.
- It works on unsorted lists. It is simple, but slow for large lists: a list of n items may need n comparisons.
Binary search
- It only works on a sorted list. Look at the middle item. If it is the target, stop. If the target is smaller, discard the upper half; if it is larger, discard the lower half. Repeat on the half that is left.
- It is much faster for large lists: 1000 items need at most 10 comparisons, because each comparison halves the list.
- When there are two middle items, pick one of them consistently (for example the lower one).
Bubble sort
- Go through the list comparing each pair of neighbouring items, and swap them if they are in the wrong order. Each pass moves the largest remaining item to its correct place at the end.
- Keep making passes until a whole pass makes no swaps.
- It is simple to code, but slow for large lists.
Merge sort and insertion sort
- Merge sort: split the list in half again and again until every list has one item, then merge the lists back together in order. It is much faster than bubble sort for large lists, but uses more memory.
Key terms
- Linear search
- Checking each item in turn until the target is found.
- Binary search
- Repeatedly checking the middle item of a sorted list and discarding half.
- Bubble sort
- Repeatedly comparing and swapping neighbouring items until no swaps are needed.
- Merge sort
- Splitting a list into single items, then merging them back together in order.
- Insertion sort
- Inserting each item into its correct place in a growing sorted part.
- Pass
- One complete trip through the list in a sort.
Quick questions on Searching and sorting algorithms
- Which search only works on a sorted list?
- Binary search: It relies on knowing which half the target is in.
- How does a linear search work?
- It checks each item in turn from the start: It stops when it finds the target or reaches the end.
- In a binary search, the target is smaller than the middle item. What happens next?
- The upper half is discarded: The target must be in the lower half.
- What is the maximum number of comparisons a binary search needs for 1000 sorted items?
- 10: 2¹⁰ = 1024, so 10 halvings are enough.
- What does a bubble sort compare?
- Pairs of neighbouring items: It swaps a pair if they are in the wrong order.
- After one pass of a bubble sort into ascending order, where is the largest item?
- At the end of the list: It 'bubbles' to the end.
- When does a bubble sort stop?
- When a pass makes no swaps: No swaps means the list is in order.
- What is the first stage of a merge sort?
- Split the list in half repeatedly until each list has one item: Then the single items are merged back together in order.
Searching and sorting algorithms: questions and answers
- What is one disadvantage of a merge sort compared with a bubble sort?
- It uses more memory. It needs extra space for the split lists.
- What is one advantage of a linear search?
- It works on an unsorted list. Binary search needs the list to be sorted first.
- A bubble sort starts on the list 5, 2, 4. What is the list after the first swap?
- 2, 5, 4. 5 and 2 are compared and swapped first.