- Computers and coding
- Classes 9-10
- 5 min read
Sorting and searching
Trace bubble sort on paper, then compare linear search with binary search and see why a sorted list can be searched in far fewer steps.
Let us begin
The big idea
Computers spend a lot of their time putting things in order and finding things. A phone contact list, a leaderboard and a dictionary all depend on sorting and searching. You can learn the classic methods with nothing but a pencil and a row of numbers.
Bubble sort puts a list in order by comparing neighbours. Go along the list; whenever the left item is bigger than the right item, swap them. After one full pass, the largest value has "bubbled" to the end. Repeat the passes until a whole pass makes no swaps; then the list is sorted.
Linear search finds a value by checking the items one by one from the start until it is found or the list ends. It works on any list, sorted or not, but in the worst case it looks at every item: 1,000 items could mean 1,000 checks.
Binary search works only on a sorted list, but it is much faster. Look at the middle item. If it is the one you want, stop. If the item you want is smaller, throw away the right half; if bigger, throw away the left half. Repeat on the remaining half. Each step halves the list, so 1,000 items need at most about 10 checks, and 1,000,000 need about 20.
This is why sorting matters: a dictionary is sorted so you can open it near the middle and jump, instead of reading from page one. The number of steps a method needs as the list grows is called its efficiency, and choosing an efficient method is a big part of computer science.
Worked examples
See how it works
Bubble sort trace
Sort [5, 2, 4, 1]. Pass 1: compare 5,2 swap to [2, 5, 4, 1]; compare 5,4 swap to [2, 4, 5, 1]; compare 5,1 swap to [2, 4, 1, 5]. Pass 2: 2,4 no swap; 4,1 swap to [2, 1, 4, 5]; 4,5 no swap. Pass 3: 2,1 swap to [1, 2, 4, 5]; then no more swaps. Pass 4 makes no swaps, so the list is sorted.
Linear search
Find 7 in [3, 9, 7, 1, 8]. Check 3: no. Check 9: no. Check 7: yes, found at index 2 after 3 checks. To find 8 would take 5 checks; to find 4, which is absent, also takes 5 checks before giving up.
Binary search
Find 23 in the sorted list [4, 8, 15, 16, 23, 42, 50]. Middle is index 3, value 16. 23 is bigger, so keep the right half [23, 42, 50]. Middle is 42. 23 is smaller, so keep [23]. Middle is 23: found in 3 checks. Linear search would have needed 5.
Try it at home
Sort and search with cards
You will need
- Eight small pieces of paper
- A pencil
- A table or floor to lay the cards in a row
What to do
- Write a different number from 1 to 50 on each card and lay them face up in a random row.
- Bubble sort them: compare the first two cards and swap if the left is bigger; move one step right and repeat to the end. Count your swaps. Repeat passes until a pass has no swaps.
- Turn all cards face down. Ask a friend to name one of the numbers. Find it by linear search, turning cards from the left one at a time, and count the checks.
- Turn them face down again (still in sorted order). Find another number by binary search: turn over the middle card, decide which half to keep, and repeat. Count the checks.
- Compare the counts. Try with sixteen cards and see how little the binary search count grows.
Practice sheet
Check what you learned
Practice sheet: Sorting and searching (Classes 9-10, Computers and coding)
- In bubble sort, when do you swap two neighbours?
- After the first pass of bubble sort, where is the largest value?
- How do you know bubble sort has finished?
- Write the list after the first pass of bubble sort on [3, 8, 1, 6].
- How many checks does linear search need to find 8 in [3, 9, 7, 1, 8]?
- What must be true about a list before binary search can be used?
- Binary search for 15 in [4, 8, 15, 16, 23, 42, 50]: which values are checked?
- Roughly how many checks does binary search need for 1,000 sorted items?
- Why is a printed dictionary sorted?
- You have an unsorted list and need to find one item just once. Is it worth sorting first?
Answer key
Answers: Sorting and searching
- When the left one is bigger than the right one.
- At the end (the last position).
- When a whole pass makes no swaps.
- [3, 1, 6, 8]: 3,8 no swap; 8,1 swap; 8,6 swap.
- 5 checks, because 8 is the last item.
- It must be sorted.
- 16 (middle), then 8 (middle of the left half), then 15: found in 3 checks.
- About 10, because each check halves the list and 2 to the power 10 is 1,024.
- So you can jump near the right place and search it quickly, like binary search, instead of reading from the start.
- No; sorting takes many steps, so a single linear search is cheaper. Sorting pays off when you will search many times.