Sorting and searching algorithms
Studying this course? Keep your progress in one place.
Key facts
- A bubble sort compares neighbouring items and swaps them if they are the wrong way round; stop after a pass with no swaps.
- A quick sort takes the middle item as the pivot, splits the rest into smaller and larger, then repeats on each sub-list.
- A binary search needs an ordered list: compare with the middle item and discard the half that cannot contain the target.
- The middle of items is position (odd ) or (even ).
- Always show each pass, pivot or sub-list, and state the result in words.
Bubble sort
A bubble sort compares neighbouring items and swaps those in the wrong order, pass after pass, until a pass makes no swaps.
A bubble sort puts a list in order by repeated passes. In each pass, compare the first two items and swap them if they are in the wrong order, then the second and third, and so on to the end.
After pass 1 the largest item is at the end. After pass 2 the second largest is in place, so each pass can stop one place earlier.
Stop when a whole pass makes no swaps.
- 1
Start
15, 8, 23, 4, 16, 9
- 2
Pass 1
8, 15, 4, 16, 9, 23 (4 swaps)
- 3
Pass 2
8, 4, 15, 9, 16, 23 (2 swaps)
- 4
Pass 3
4, 8, 9, 15, 16, 23 (2 swaps)
- 5
Pass 4
No swaps, so the list is sorted
Worked example
Use a bubble sort to put 15, 8, 23, 4, 16, 9 into ascending order.
- 1
Pass 1: 8, 15, 4, 16, 9, 23 (4 swaps). The largest item, 23, is in place.
- 2
Pass 2: 8, 4, 15, 9, 16, 23 (2 swaps).
- 3
Pass 3: 4, 8, 9, 15, 16, 23 (2 swaps).
- 4
Pass 4: no swaps, so the list is sorted.
When does a bubble sort stop?
The middle item
The middle item of items is in position if is odd and if is even.
Quick sort and binary search both need the middle item.
- gives the 5th item.
- gives the 4th item.
- gives the 6th item.
Apply the rule to each new sub-list, renumbering from 1.
- N oddposition
- N evenposition
Which position is the middle of 8 items?
Quick sort
A quick sort picks the middle item as pivot, puts smaller items to its left and larger to its right, then repeats on each sub-list.
Quick sort is a divide-and-conquer sort.
- Choose the middle item as the pivot.
- Write items smaller than the pivot to its left and larger items to its right, keeping their original order within each side.
- The pivot is now in its final position.
- Repeat on each sub-list, left first, until every sub-list has at most one item.
- 1
Choose the pivot
the middle item of the list
- 2
Split
smaller items left, larger right, order kept
- 3
Fix the pivot
it is now in its final place
- 4
Repeat
on each sub-list, left first
Worked example
Use quick sort on 27, 14, 35, 8, 22, 41, 11, 19.
- 1
There are 8 items, so the pivot is in position 5: 22. This gives 14, 8, 11, 19 | 22 | 27, 35, 41.
- 2
Left sub-list (4 items): pivot is the 3rd item, 11. This gives 8 | 11 | 14, 19.
- 3
Right sub-list (3 items): pivot is the 2nd item, 35. This gives 27 | 35 | 41.
- 4
Sub-list 14, 19 (2 items): pivot is the 2nd item, 19. This gives 14 | 19.
After the first pivot, what is true of the pivot?
Binary search
A binary search of an ordered list compares the target with the middle item and discards the half that cannot contain it, repeating until it finds the target or nothing is left.
A binary search finds an item in a list that is already in order.
- Find the middle item. If it equals the target , stop.
- If is smaller, discard the middle item and everything after it. Otherwise discard it and everything before it.
- Repeat on what remains.
- If no items remain, is not in the list.
- 1
Find the middle
compare it with the target T
- 2
Equal?
if yes, stop: found
- 3
Discard half
smaller: drop the middle and everything after; larger: drop the middle and everything before
- 4
Repeat
nothing left means T is not in the list
Worked example
List: 3, 8, 12, 17, 21, 25, 29, 34, 38, 42, 47, 53, 60. Search for 42, then for 20.
- 1
For 42: 13 items, the middle is the 7th item, 29. , so discard 29 and everything before it.
- 2
Remaining: 34, 38, 42, 47, 53, 60. The middle is the 4th item, 47. , so discard 47 and everything after it.
- 3
Remaining: 34, 38, 42. The middle is 38. , so discard 38 and everything before it. The remaining item is 42, so 42 is found.
- 4
For 20: the middles are 29, 17, 25 and 21 in turn. After 21 is compared, no items remain.
What must be true of a list before a binary search?
Choosing between methods
Bubble sort is simple but needs many passes on long lists; quick sort usually needs far fewer comparisons; a binary search halves an ordered list each time.
A binary search needs at most about comparisons, because a list of items is halved each time. This is far fewer than checking every item in turn.
Whichever method you use, show each pass or sub-list clearly, give the final result and state any conclusion (found or not found) in words.
Bubble sort
- Swaps neighbours
- Many passes for long lists
Quick sort
- Splits around a pivot
- Usually far fewer comparisons
Binary search
- Needs an ordered list
- Halves the list each time
Which method finds an item in an ordered list fastest?
Try an exam question
A list of numbers is 19, 7, 23, 12, 5, 16. (a) Perform one pass of a bubble sort, writing down the list after the pass. (b) Use the quick sort algorithm, with the middle item as pivot, to put the list into ascending order, showing the first pivot and its two sub-lists.
[4 marks]
- [1]After one pass: 7, 19, 12, 5, 16, 23.
- [1]First pivot is the 4th item, 12, giving sub-lists 7, 5 | 12 | 19, 23, 16.
- [1]Left sub-list sorted as 5, 7 and right sub-list sorted as 16, 19, 23 using further pivots.
- [1]Final list 5, 7, 12, 16, 19, 23.
That's the notes covered.
Carry on to the next subtopic.
Try a question
What is the list after the first pass?
1 mark, marked against the mark scheme
What is the list after the first pass?
1 mark, marked against the mark scheme