Track: Unplugged · Lesson 5 of 10 · Ages: 7+ · Time: 35 minutes
Put these in order from smallest to biggest: 5, 3, 6, 1, 4, 2. Easy, right? You just looked at them all at once and your brain worked it out.
A computer cannot glance at a whole row. It compares two things at a time. So how can it sort a long list? Let’s find out with a game.
Beep says I can only look at two cards at once, the one on the left and the one next to it. I need a clear method. Beep boop!
What you need
- Number cards from 1 to 6 (make them from paper, or use playing cards).
- A flat surface.
- A friend, if you want a race.
Grown-ups Sorting is one of the most important jobs computers do, so it is a great first look at an algorithm that has more than one step. The method here is called bubble sort. It is not the fastest way, but it is the easiest to understand. If your child is just 6, use only the numbers 1 to 4.
The rule: compare two neighbours
To compare means to look at two things and decide which is bigger. Put the cards in a row, face up, in this order:
5 3 6 1 4 2
Here is the method, which is called bubble sort. Start at the left end and do this:
- Look at the first two cards.
- If the left one is bigger, swap them. If not, leave them.
- Move along by one card, and look at the next two cards.
- Keep going until you reach the end of the row. This is one pass.
- Do another pass from the start. Keep doing passes until you make a whole pass with no swaps. Then the cards are sorted!
Pixel says Why “bubble”? The biggest card floats along to the end of the row, like a bubble rising in water. Meow!
Pass 1, step by step
Start with 5 3 6 1 4 2. The two cards being compared are shown in order.
| Compare | What happens | Row after |
|---|---|---|
| 5 and 3 | 5 is bigger, swap | 3 5 6 1 4 2 |
| 5 and 6 | 5 is smaller, leave | 3 5 6 1 4 2 |
| 6 and 1 | 6 is bigger, swap | 3 5 1 6 4 2 |
| 6 and 4 | 6 is bigger, swap | 3 5 1 4 6 2 |
| 6 and 2 | 6 is bigger, swap | 3 5 1 4 2 6 |
The biggest card, 6, floated all the way to the end, so it is in the right place. Now do pass 2 from the start. Here is what the row looks like after each pass:
| After pass | Row |
|---|---|
| 1 | 3 5 1 4 2 6 |
| 2 | 3 1 4 2 5 6 |
| 3 | 1 3 2 4 5 6 |
| 4 | 1 2 3 4 5 6 |
| 5 | 1 2 3 4 5 6 (no swaps, so we are done!) |
After pass 4 the row was already in order. Pass 5 had no swaps. That is how the computer knows it has finished.
Play the race
- Shuffle the cards and lay them in a row, face up.
- Race a friend or a timer using the neighbour method. You may only compare and swap two neighbours at a time.
- Next, try sorting the same cards any way you like. Is it faster?
- Now try 10 cards. How much longer does the neighbour method take?
You will probably find that your brain is amazing at sorting a few cards by looking at the whole row. But a computer cannot look at everything at once, so it needs a careful method.
Why does it matter?
Computers sort things all the time. They put names in order in a list, put search results in order, and arrange your music from A to Z. Programmers have invented lots of sorting methods. Some are much quicker than bubble sort, especially for very long lists.
Did you know? The more cards there are, the more compares you need. A sort that is fine for 6 cards can take a very long time for a million, so programmers love finding faster methods.
Challenges
Try it Sort these five cards with bubble sort and write the row after every pass: 7, 2, 9, 4, 1.
Show a hint
In pass 1, the biggest card (9) floats to the end. Remember to stop when a whole pass makes no swaps.
Show the answer
Start: 7 2 9 4 1 Pass 1: 2 7 4 1 9 Pass 2: 2 4 1 7 9 Pass 3: 2 1 4 7 9 Pass 4: 1 2 4 7 9 Pass 5: 1 2 4 7 9 (no swaps, done!)
Try it Sort from biggest to smallest instead. What one thing do you change in the rule?
Show the answer
Swap when the left card is smaller instead of bigger. Everything else stays the same.
What you learned
- To compare is to look at two things and decide which is bigger.
- Bubble sort swaps neighbours that are in the wrong order, pass after pass.
- You are done when a whole pass makes no swaps.
- Computers compare two things at a time, so they need careful methods.