Activity 8

Beat the Clock—Sorting Networks

Summary

Computers are very fast, but there is still a limit to how quickly they can solve problems. One way to make things faster is to use several computers to solve different parts of a problem at the same time. In this activity, we use sorting networks. A sorting network is a way of arranging things so that several comparisons (checking which number is bigger or smaller) can happen at the same time.

Curriculum Links

• Mathematics: Number level 2 and up. Exploring number: Greater than, less than

Skills

• Comparing
• Ordering
• Developing algorithms (step-by-step instructions for solving a problem)
• Co-operative problem solving

Ages

7 years and up

Materials

This is an outdoor group activity. You will need:

• Chalk
• Two sets of six cards (copy the Sorting Networks photocopy master onto card and cut it out)
• A stopwatch

Sorting Networks

Before you start, use chalk to mark out the network on the ground, like a court.

Instructions for Children

This activity will show you how computers sort jumbled-up numbers into order using something called a sorting network.

1. Get into groups of six. Only one team uses the network at a time.
2. Each team member takes a numbered card.
3. Each person stands in a square on the left-hand (IN) side of the court. Your numbers should be mixed up, not in order.
4. Move along the lines that are marked on the ground. When you reach a circle, you must wait until someone else arrives there too.
5. When another team member joins you in the circle, compare your cards. Whoever has the smaller number takes the exit on their left. Whoever has the bigger number takes the exit on their right.
6. When you reach the other end of the court, check: are you in the right order?

If a team makes a mistake, they must start again. Make sure everyone understands how a node (circle) works: the smaller number always goes left, and the larger number always goes right.

Variations

1. Once everyone knows how the activity works, use a stopwatch to time how long each team takes to get through the network.
2. Try using cards with bigger numbers, like the three-digit numbers on the photocopy master.
3. Make cards with even bigger numbers that take more effort to compare. Or use words instead of numbers, and put them in alphabetical order.

Extension Activities

1. What happens if the smaller number goes right instead of left, and the bigger number goes left instead of right? (The numbers will end up sorted backwards.)

Does the network still work if you use it backwards? (Not always — see if you can find an example where the numbers come out in the wrong order.)

1. Try designing smaller or bigger networks. For example, there is a network that can sort just three numbers. Try to figure out what it looks like on your own.

1. Look at two different networks that can each sort four numbers. Which one is faster? (The second one is faster. In the first network, every comparison has to happen one after another — this is called serial processing. In the second network, some comparisons happen at the same time — this is called parallel processing, and it works faster.)

1. Try building an even bigger sorting network.

1. Networks can also be used to find the smallest or largest number in a group. For example, a network with eight numbers going in can be built so that only one output shows the smallest number. The rest of the numbers get left behind at dead ends in the network.

1. Think about jobs in everyday life. Which ones can be done faster by having more people help, and which ones can't? For example, cooking a meal would take much longer if you only had one stove burner, because everything would have to cook one at a time instead of all together.

What's it all about?

As people use computers more and more, we want them to handle information as quickly as possible.

One way to make a computer faster is to write programs that use fewer steps (you can see this in Activities 6 and 7).

Another way to solve problems faster is to have several computers work on different parts of the same task at the same time. For example, in the six-number sorting network, a total of 12 comparisons are needed to sort the numbers. But since up to three comparisons can happen at the same time, the whole job only takes as long as 5 steps would take. This parallel network sorts the list more than twice as fast as a system that can only do one comparison at a time.

Not every task can be finished faster just by splitting it up between more workers. Here's an example: imagine one person digging a ditch that is ten metres long. If ten people each dug one metre of it, the job would finish much faster. But this trick wouldn't work for a ditch that is ten metres deep — nobody can dig the second metre down until the first metre has already been dug. Computer scientists are still working hard to find the best ways to break problems into parts so that computers can solve them together, in parallel.