Algorithms and algorithmic thinking are central to learning about computing. Unfortunately, an algorithm, as a thing itself, can be rather abstract; it can be difficult for students to understand what the algorithm is doing and how the execution of the algorithm leads to the desired end result. Students often need some way of seeing how an algorithm works on a particular problem.

There are several ways of doing this. Dry-running algorithms with pen and paper works in some cases. More complex algorithms benefit from other visualisations, particularly animations. Network algorithms are well suited to this, but the most common visualisations are for sorting algorithms. The animations range from shuffling bars, to sounds, and even Hungarian folk dancers! While these visualisations are good at showing how the algorithm operates, the student still has to keep in mind both the algorithm’s specification and its behaviour, including the values of any variables used to keep track of where execution is in the algorithm.

Sorting networks do a lot to address this problem. A sorting network is an executable visualisation of an algorithm. Figure 1 shows a sorting network and Figure 2 shows how one works in practice. The objects to be sorted enter the network on the left, one on each horizontal line. The vertical bars show when two objects are compared; if they are out of order, they are swapped so the smallest is at the top of the vertical bar. When the objects leave the sorting network on the right, they are in order, top to bottom. Sorting networks can be any size, but become progressively larger and more complex the more items they sort. Figure 3 shows a sorting network for eight items.

Figure 1. A four-element sorting network. Items to be sorted enter at the left. Vertical lines show comparisons and possible swaps. When the items emerge from the right, they are in sorted order, smallest at the top.

Figure 2. An example of a sorting network in action.

Figure 3. An eight-item sorting network.

Sorting networks unplugged

Sorting networks work as an “unplugged” activity, where students move through a physical sorting network. It makes a good group activity where the students become the items being sorted. We have made large sorting networks from coloured masking tape on the floor of a room (figures 4 and 5), with people holding large playing cards as the items to be sorted. (Coloured masking tape can be bought in any hardware store and we bought a cheap pack of giant playing cards on eBay.) In this presentation, students literally step through the algorithm, being acted on it as the algorithm progresses.

Figure 4. A six-item sorting network laid out on a floor.

Figure 5. Another view of a six-item sorting network.

The instructions for the participants are simple. People start in an arbitrary order at the start of the network, then walk forwards along their line until they reach a junction with a comparison link (we marked these with crosses). There they wait until they see another person waiting at the other end of the comparator. The two people compare their cards and swap if necessary. (We found it helpful to label one side of the room “small” and the other “large” to remind people the order when comparing.) Then, both people move forward until the next comparison link. (You can do swaps either by people swapping cards or, more fun, by walking along the comparison lines.) Figure 6 shows this in action. When people reach the end of the network, they should be sorted.

If something goes wrong and the output isn’t sorted, ask people to walk backwards until they find a comparison in the wrong order, fix it, then run the algorithm again. This brings out the computational thinking skill of debugging.

Figure 6. People being sorted by a sorting network

Computational thinking with sorting networks

While having people run through a sorting network is a fun activity in itself, it doesn’t explore or develop much computational thinking. However, it can be the basis of some work in this area. (CS Unplugged has a good resource on sorting networks with further ideas than given here.)

One thing students can consider is how they can know that the network works in every case, which means they need to consider how many ways there are of ordering the inputs, which feeds into ideas of program validation and testing. They may ask questions about whether the sorting network will work if the items are to be sorted in reverse order, or if the sorting network will sort some objects if they’re fed in at the right and come out at the left.

They may also consider what the network should do when two or more items have the same values to be sorted by, introducing the idea of stable and unstable sorts. The nature of the sorting network also allows a teacher to draw out notions of parallel execution. For instance, in the eight-item sorting network, each of the the first comparisons can be done simultaneously with at least one other. This can reduce the time taken to traverse the network. This is exploited for real in GPUs, where the parallel, one-way pipelines of sorting networks are a good fit for the parallel structure of a GPU.

Making new networks

One of the more immediately accessible exercises with sorting networks is having students build their own networks of different sizes. At first, this is a challenge, but once people know a “trick” they can easily develop reasonably small (though not necessarily optimal) networks of any size.

A two-item sorting network is trivial: it has a single comparison (figure 7). A three-item network can be built from this: first, do sufficient swaps to move the largest item to the bottom line, then sort the remaining two items. This is shown in figure 8. The first two swaps move the largest item, but the other two items could be an any order afterwards. The final swap puts them in order.

A four-item network is built from a three-item network in the same way. First, do three swaps to move the largest item to the bottom, then use the existing three-item network to sort the rest. Larger networks can be built up in the same way. students can make and test their own networks this way, gaining an understanding of how to decompose a problem into smaller subtasks. In fact, this way of building up sorting networks allows you to sneak in recursion in an easy-to-swallow form!

Again, students can use this basis to explore concepts such as the number of comparisons needed for each size sorting network, and the “depth” of the network (how many comparisons at item must go through). These can be used to prompt connections to series and Pascal’s triangle and back to counting combinations.

Figure 7: A two-item sorting network

Figure 8: A three-item sorting network

Figure 9: A four-item sorting network, highlighting the three-item network embedded within it.

This approach to building up the sorting network is an example of a selection sort: the network selects the largest item and puts it in the correct place, then selects the next largest item and puts it in place, and so on. You can also show insertion sorts the same way: first, sort the n-1 items, then do sufficient swaps to put the last item in its place. This leads to the same networks as selection sorts, showing that they have the same worst-case complexity. Bubble sorts also give similar sorting networks, especially if you include the trick of not sorting the guaranteed largest items after each pass.

Unfortunately, while it’s easy to explain, this approach doesn’t lead to the smallest possible sorting networks, especially for larger networks. For instance, the four-wire network in figure 9 has six comparators, while the four-wire network in figure 1 only needs five. An extension activity could be to ask these children to come up with other sorting networks that are still correct, but which have fewer comparisons. The wikipedia article on sorting networks lists the minimum of comparators for different numbers of items. The sorting algorithms that generate smaller sorting networks are more complex than the ones found in schools, but could make the subject of a detailed investigation or project into a particular area.

Wrapping up

Sorting networks give a good vehicle for describing algorithms in a way that is immediate and visually appealing. They allow teachers to present algorithms in ways that don’t use a computer or even a pen and paper. A kinesthetic activity can make a good change in style, especially when used with younger children.

Appendix: optimal sorting networks

It’s not easy to find good examples of optimal (smallest) sorting networks at different sizes. We’ve put some below (for five, six, and seven inputs). The Wolfram sorting network demo tool allows you to look at other sorting networks.

 

---

by Neil Smith (n.smith@open.ac.uk, Open University) and Helen Caldwell (helen.caldwell@northampton.ac.uk, University of Northampton)

This post first appeared in :
Smith, N. and Caldwell, H. (2016). Literally stepping through algorithms: visualising algorithms with sorting networks. Math+Code ‘Zine: Exploring math through code Vol 2, Issue 1 http://researchideas.ca/mc/stepping-through-algorithms/ Faculty of Education, Western University, Ontario, Canada.

See more of Helen Caldwell & Neil Smith’s ideas in their book …

Teaching Computing Unplugged in Primary
Schools – Exploring primary computing through practical activities away from the computer
Helen Caldwell & Neil Smith

Important aspects of the fundamental principles and concepts of computer science can be taught without any hardware. Children can learn to analyse problems and computational terms and apply computational thinking to solve problems without turning on a computer. This book provides lesson examples and everyday activities to help teachers and pupils explore computing concepts in a concrete way, accelerating their understanding and grasp of key ideas such as abstraction, logic, algorithms and data representation.