Recursive Selection Sort

published: Wed, 24-Nov-2004   |   updated: Mon, 16-May-2005

I was browsing through the access logs for my website and I came across a search phrase that was used to access my site from Google: "recursive selection sort in vb". We'll ignore the VB part (I'm not in the mood for writing VB code tonight), but the first part got me thinking. Since I'm waiting for my ride home, and I need a change from my real, paying work, let's see what we can do.

You see, selection sort is never written as a recursive function. It's simple enough to be written as one loop inside another.

Let's recap. The selection sort algorithm works like this. First find the smallest item in the list. Swap it with the first item in the list. Now consider the sublist that excludes the first item and find the smallest item in this sublist. Swap it with the first item in the sublist (the second item in the overall list). Continue like this until your sublist is only one item long.

The interesting thing about this sort is that it's very quick if the items are large or if they take a long time to swap. If you think about it, every item is moved directly into its final resting place, through a swap operation (which is a set of three moves). So just taking into account the moves, if you have N items you'll perform, in the worst case, 3*(N-1) moves.

You will be doing a whole lot more comparisons though. The first time through you'll do (N-1) comparisons. The second time through you'll do (N- 2) comparisons. And so on. Adding up all these comparisons you get N*(N- 1)/2 as the number of comparisons.

So, if your comparisons are very quick compared to your moves, you'll have a O(n) algorithm. If it's the other way round, you'll have a O(n²) algorithm.

Anyway, it's very easy to convert this algorithm into code using two loops, one inside the other. (And note that having these two loops constructed in this fashion also points to the algorithm being O(n²).)

procedure IterativeSelectionSort(A : TIntArray; aStart, aEnd : integer);
var
  i, j : integer;
  IndexOfMin : integer;
  Min : integer;
begin
  for i := aStart to aEnd do begin
    IndexOfMin := i;
    Min := A[i];
    for j := i + 1 to aEnd do begin
      if (Min > A[j]) then begin
        Min := A[j];
        IndexOfMin := j;
      end;
    end;
    if (i <> IndexOfMin) then begin
      A[IndexOfMin] := A[i];
      A[i] := Min;
    end;
  end;
end;

Now to think about this algorithm recursively, you just have to reread the description of the sort. Essentially it says this: find the smallest item in the list and swap with the first item. Shrink the list by one item (the first), and perform the same algorithm on the smaller list. If there's only one item in the sublist, it's already sorted.

We've defined a recursive algorithm here, it's going to be used on smaller and smaller lists (and therefore has a chance of stopping), and we have a termination test to make sure that it does stop.

Much as you'd expect, the recursive selection sort implementation therefore looks like this:

procedure RecursiveSelectionSort(A : TIntArray; aStart, aEnd : integer);
var
  j : integer;
  IndexOfMin : integer;
  Min : integer;
begin
  if (aStart = aEnd) then
    Exit;

  IndexOfMin := aStart;
  Min := A[aStart];
  for j := aStart + 1 to aEnd do begin
    if (Min > A[j]) then begin
      Min := A[j];
      IndexOfMin := j;
    end;
  end;
  if (aStart <> IndexOfMin) then begin
    A[IndexOfMin] := A[aStart];
    A[aStart] := Min;
  end;
  
  RecursiveSelectionSort(A, aStart + 1, aEnd);
end;

Notice a couple of things here. First is that it's more difficult to make generalizations about the speed characteristics of this algorithm: the outer loop is no longer explicit as in the iterative case, it's now implicit in the recursive call; but it's harder to analyze. Second, if we go back to the iterative version from the recursive version, you can see how easy it is to remove recursion that occurs as the last statement of the recursive routine's code (this is known as end-recursion). In brief, end-recursion is removed by being replaced with a loop.

So all in all a simple enough algorithm. And one that helped pass the time as I waited for my ride home.