One of the topics that I always found a challenge to teach was that of sorting. I struggled with learning the concept myself as a student and I always found it difficult to make it tangible and visible for students.
I did all the chalk and talk things that I could think of. But the best way that I could demo it off-computer was with a deck of cards numbered 1-10.
I put 10 chairs in a row, side by each, and then one off to the side. I had 10 students sit in the chairs in random order with their numbered cards and had them demonstrate sorting based upon the number they were holding.
The goal was to develop an algorithm where the 10 people holding the cards were to move and put themselves in order from 1-10 or 10-1.
The rules were:
- only one person could stand at a time
- there were two things that could be discussed
- am I bigger (smaller) than you?
- go sit in the chair over there
- come back and sit here
- are we in order?
Our starting point was always the Bubble Sort. Technically, that was all that I needed to address the expectations from the curriculum.
A3.4 create a sort algorithm (e.g., bubble, insertion, selection) to sort data in an array;
From the Ontario Curriculum Grades 10 to 12 – Computer Studies.
But, you can’t stop with just one. I also used to talk about a Selection Sort and we would talk about the difference in algorithms and ended up comparing each for efficiency. A final kick at the sorting cat was the Quick Sort. There is an increasing level of sophistication in the coding involved.
That led to a good discussion about why you might want to choose one over the other. It also was a good rationale for building a personal library of algorithms. Sorting is used so frequently, why should you start from scratch every time you need a sort? Bringing in something that you know works and modifying it for the purpose of the program makes so much sense.
Recently, Alfred Thompson shared his thoughts in a post “How Fast Can You Sort a Deck of Cards?” Working with a deck of cards is certainly more aggressive than my cards 1-10. You have to deal with the concept of Jokers, are Aces high or low?, do you also sort by colour?, do you also sort by suit? It’s a scenario that can lead to a great deal of discussion. I like it.
Embedded in Alfred’s post is a link to a resource demonstrating various Sorting Algorithms.
This is fabulous. If you want to see how a Bubble Sort works, just select a cell and watch it do its thing. I think the best demonstration is the Reversed data set. There, every piece of data is out of order so you get the full effect.
But that’s just the academics of it.
In the top left corner, there’s a button to “Play All”. This is addictive as you watch all of the sorts with the various data set permutations do their thing. This truly is the beauty of computer science. Beyond this, it answers the question of why there are different sorting algorithms. You’ll notice on first run that they don’t all finish at the same time. Some algorithms are definitely better than others. Code demonstrating each sort is available under the chart.
Learning how to write code to sort can be a challenge. But, it’s something that you have to do at some point if you’re going to be a programmer.
I just found this resource a wonderful way to demonstrate different algorithms and a visual rationale for each.
It’s a definite keeper. Thanks, Alfred for turning me to this resource.