Do beginners even need to learn sorting algorithms? Let’s face it most modern programming environments have a sort function built in. In the so-called real world just about the only people who write sorting algorithms have PhDs in math or computer science and have likely published papers in peer reviewed journals on the sorting subject. So why take up time in a first programming course to talk about sorting? Because its good for them! Well sort of.
I was looking through the first textbook I wrote some 11 years ago and finding that it include both the bubble and selections sorts. Now these are terribly performing sorts. No one uses these. Quick sort perhaps. Maybe Insertion sort. Bubble sort? What was I thinking! As best I can recall I was thinking about helping explain how arrays worked with loops. It was more about developing an algorithm and seeing how it worked with real (or realish) data. Oh and if I recall correctly, the publisher asked me to make sure I covered sorting and searching. But maybe that is me trying to blame someone else. In a more advanced course one would use different sorting algorithms to learn about algorithm complexity, performance and probably also discuss Big-O notation. That works as a good excuse to talk about different sorting algorithms for many.
Students understand what sorting is all about. Well they don’t understand all of what it is about but at least if you ask students to sort data by hand they can usually do it. In fact asking students to sort data, perhaps on index cards, and asking them to think through the process they use can be very helpful. This helps them understand the complexity. The value though is really about understanding algorithm creation and translating that into code. Having to involved a number of important concepts like arrays, loops, and decision structures is also a good thing.
I think today I would teach the Quick Sort. It has all the goodness of other sort PLUS it involves recursion. Recursion is still a bit of magic to me. What it has taken me a while to really appreciate recursion I do now. The typical recursion example is really looping – things like calculating the Fibonacci Sequence. That’s not a bad thing but an application that requires recursion is better, my opinion, for getting students to really appreciate its power.
But I wonder if there are better algorithms to use as teaching tools? We, the teaching community, should probably be looking for some. Perhaps some that students are actually likely to have to implement some day. What do you think? Are sort algorithms essential? Why? What sort or sorts do you think students should learn? Or is there a better problem that solves the same issues in learning programming and algorithm development?