|Lesson 9: Sorting Nets|
This lesson was adapted from a freely available sample lesson in
Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See
for more information.
Motivation:This is an excellent warm up or ice breaking exercise. It demonstrates a task computers are particularly good at: sorting. Even though sorting requires a lot of computation, this activity takes advantage of the fact that much of this computation can be done at the same time ("in parallel"), thereby accomplishing a lot in a very few steps.
Conclusion:Some problems are easy to break up into many sub-problems which can be solved simultaneously, with separate computer processors working on each sub-problem. In Lesson 8 we investigated a number of different sorting methods in which a single comparison was made at each step, and the better algorithms were the ones using the fewest number of comparisons. The sorting network in this activity had a number of comparisons occurring at the same time. This is called "parallel processing". The most important factor in determining how fast we can sort in this case wasn't the number of comparisons (which corresponds to the number of comparator nodes in the sorting network), but rather the "depth" of the network - the number of levels from start to finish. Ask the students to recall the process of sorting film canisters. Which technique seems to be more efficient? If the parallel sorting network seems more efficient, why don't we always sort in parallel? Why not solve every problem "in parallel"?
Discuss processes from everyday experience that can be accelerated using parallelism. For example, cooking a meal would be a lot slower using only one burner because items would have to be cooked one after the other. Have the kids think of other examples from their lives where parallelism occurs. Can the students think of instances where parallelism doesn't work? Some process are inherently sequential: If you had enough arms, you could probably put your pants and shirt and hat on all at once (in parallel), but no number of arms would let you put your shoes on at the same time you put your socks on.
Evaluation:Have the students draw a 3-sorter, label the parts of the sorter (inputs, comparison nodes, and outputs), and then describe how it works in writing. In assessing their work, look for explanations which indicate understanding beyond just "we went through the network and came out sorted." They might say something about parallelism, or about the fact that they came out sorted no matter how they started, or that they came out in order even though they didn't compare themselves with everyone else in the network.
Extensions:Any kind of comparison can be used at the comparison nodes of the network. For advanced students, for example, a statistical hypothesis test could be done at each node.
The students may be interested in exploring whether or not the network sorts if it is used backwards. It won't, necessarily. See if the students can find an example input which comes out in the wrong order. Use this opportunity to reinforce the notion that something which sometimes works, and sometimes doesn't, isn't much help in solving a problem.
Discuss the fact that the sorting network for a particular number of inputs is not unique. Let the students try to come up with different networks for 4 inputs. Which runs faster? How can you tell?
Design a network to find the minimum or maximum value of the inputs.
It is an exercise in simple combinatorics to find the total number of ways the inputs can be arranged. These arrangements are called permutations, and for n inputs there are n! = n (n-1)...2 of them. (n! is "n factorial") One way to explain this is to note that there are n different ways of selecting the first input value from among the n original items. Then, for each of these n ways, there are (n-1) ways of selecting the second value, for a total of n(n-1) ways of selecting the first two values. For each of these n(n-1) ways, there are (n-2) ways of selecting the third input, for a total of n(n-1)(n-2) ways of selecting the first 3. Continue in this way to see that there are n! total ways of arranging the n inputs.
It is difficult to determine whether or not a given sorting network works for every possible input. The only way to check appears to be to try all possible permutations as inputs, and see if they always come out sorted. Advanced students can be asked how long it would take to check a network with, say, 100 inputs, if we could try a million permutations each second. (The answer is that the sun will have long since burned out.)
A clever variation of the sorting net activity, suggested by Richard Clift, is to run the activity without any sorting net at all! On the playground, or in the classroom, set up instruction cards telling students which location to go to in order to meet up with another student to compare values. At that location, you'll have pre-placed a card explaining where the larger should go from there, and where the smaller should go. At those locations they'll meet another student, compare, and so on. The "net" only exists logically, and not physically. Thus, in this imaginary net, the playground locations play the role of comparison nodes, and the instruction cards at each location replace the paths indicating where to go next. When they all arrive at, say, a row of numbered desks in order, they'll be quite intrigued.
If you'd like to try a bigger sorting net, here's the map of an 8-sorter network.
This lesson was adapted from a freely available sample lesson in Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for more information.