Sorting from the top and from the bottom

I've been meaning to write this post for a couple of weeks, but some times life just gets in the way.

I've always thought it important to arm students with as many different tools with which to attack problems as possible. As such, the courses I teach use a number of different languages, each highlighting a different paradigm and thought process. The hope is that by the end of the sequence, they can look at problems from many different angles.

In my advanced placement classes, we recently studied sorting algorithms. It think the quicksort is a good example of a problem that can be looked at from multiple points of view.

In my experiences talking to teachers and students who cut there teeth using languages like Java, C, or C++, much of the discussion deals with the actual partitioning of the array. Comparing elements, swapping them and arriving in the middle. One might end up with something like this as a first cut:

 1:  public void qsort(int[] a,int l, int h)
 2:  {
 3:  if (l>=h)
 4:    return;
 5:  
 6:  /* Just use lowest index as pivot for now */
 7:  int pivot = a[l];
 8:  int low=l;
 9:  int high=h;
10:  
11:  /* partition the data set around the pivot value */
12:  while (l<=h)
13:  {
14:    while (a[l]<pivot)
15:      l++;
16:    while (a[h]>pivot)
17:      h--;
18:    if (l<=h)
19:    {
20:      int tmp=a[l];
21:      a[l]=a[h];
22:      a[h]=tmp;
23:      l++;
24:      h--; 
25:    }
26:  }
27:  
28:  /* sort items below and above the pivot */
29:  qsort(a,low,l-1);
30:  qsort(a,l,high);
31:  
32:  }

A fair amount of time and detail is spent dealing with the low level movement of data within the array . This is important – good stuff, but it takes the emphasis away from the higher level elegance of the algorithm.

The quicksort can be described as:

1. If the size of the list is <= 1, return.
2. 1. Select a pivot element
   2. Generate the list L of items smaller than the pivot
   3. Generate the list H of items larger than the pivot
   4. the sorted list is qsort(L)+pivot+qsort(R)

Having seen some scheme in their intro class, our students have a tool with which we can describe the quicksort in terms much closer to the description (allowing for the fact that this doesn't deal with multiple values equal to the pivot correctly):

 1:  (define makefilter
 2:    (lambda (op x)
 3:      (lambda (n) (op x n))))
 4:  
 5:  (define qsort 
 6:    (lambda (l)
 7:      (cond ((null? l) '())
 8:            (else (append (qsort (filter (makefilter > (car l)) l))
 9:                          (list (car l))
10:                          (qsort (filter (makefilter < (car l)) l)))))))

This allows us to discuss the quicksort at a much higher level and focus on things like selecting a good pivot or the analysis of the run time. I believe this makes it much easier to really understand what's going on.

Having discussed it in this functional context, we can also look at the same thing in a scripting language such as python:

1:  def qsort(l):
2:      if len(l)<=1:
3:          return l
4:      else:
5:          return qsort([x for x in l[1:] if x <= l[0]]) + [l[0]]+\
6:              qsort([x for x in l[1:] if x > l[0]])
7:  

Again, the focus is on the algorithm, not the array or list manipulation.

Looking at the problem from both the more abstract side, which in this case functional languages allow, and the more concrete, as we did in Java gives our students more tools with which to attack problems.

Just some food for thought.