Earlier today I saw a facebook post asking for thoughts on teaching sorting. The question was specifically not about motivations like having the class act out sorts or sort cards but rather about the coding.

I've been meaning to write about this since last summer when I attended Owen Astrachan's talk on the same subject.

Early in my career when teaching sorting I developed the n^2 sorts as standalone routines just as they're presented in most books but as I gained more experience as a teacher, I changed it up to build the sorts (at least some of them) from existing concepts.

Let's look at the selection sort.

We can demonstrate it by arranging an already dealt hand. Find the smallest card place it all the way at the left. The next smallest, next to it. Repeat until done.

This is actually a very easy algorithm to develop using code the kids have already written.

By the time we do sorting, students have already written the code to find the smallest or largest in a list time and time again. We've also used that concept in developing other algorithms like the one I wrote about here. Assuming we've covered the ArrayList, We can easily code up a sorting type algorithm (excuse any little Java errors, I've been teaching this in C++ for the past 3 years):

  ArrayList<Integer> sort(ArrayList<Integer> a){
      ArrayList<Integer> result = new ArrayList();
      int min_index;
      int value;
      for (int i = 0; i < a.length();i++) {
          min_index = findMinIndex(a);
          value = a.get(min_index);
          a.remove(min_index);
          result.append(value);
      }
      return result;
  }

This won't be efficient due to hidden complexity but it's very easy to write and understand the algorithm

From here it's a simple matter to code this algorithm in place - swapping the next smallest item each time. This time coded with an array::

  int min_index;
  int value;
  for (int i = 0; i < a.length();i++) {
      min_index = findMinIndex(a,1,a.length()); // find min excluding what's sorted so far
      value = a.get(min_index);
      swap(a[i],a[min_index]);
  }

If you want, you can then break out the findMinIndex routine and the swap so that kids see all the code in one place but regardless, this is an easy, incremental way of teaching selection sort.

You can do something similar with insertion sort. Start with the code to insert an item into an already sorted list. Write that as a routine and then put a loop around it to complete the sort.

Developing routines like this incrementally has a number of advantages. The code is simpler, it reinforces old concepts, and it gives students additional practice in composing more complex solutions from building blocks.

You can use a similar approach to coding the more advanced sorts but I'll save those ideas for a future post.