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.
- Insertion sort (OCR): take each item in turn and insert it into the correct place in the sorted part at the start of the list.
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.