The Shell Sort

Yes, I know Delphi comes with a number of sorting routines, but I thought I'd describe a shell sort as it is fascinating little sort routine that is easily understood and a very fast routine.

[Steve: Although the "Shellsort" algorythm was first published by Donald Shell (as pointed out by Anthony Mills, thanks Anthony), this 'Shell Sort' uses a different approach that would be closer to a "Bubble Sort" with some changes. I therefore take a little 'artistic licence' in describing it in ways that people can visually understand]

The name "Shell Sort" comes from those games that are played by the magician, conman, or simply the swift of hand when they try to get money from the average passerby. Having usually 3 shells, a small coin or marble is placed under one of the shells. The shells are then swapped around at speed and the passerby is asked to bet on which shell contains the marble.



The shell sort routine does that same swapping around, but only to place all the shells in order. Consider that each shell is numbered, in this case, 1 to 5, but we'll first get our 'swift of hand' guy to jumble them up a little.



For the purposes of this blog, I'll limit the sort to only 5 integer numbers (or shells) although these could be words or extended reals or whatever. So long as you can compare them to see which is the greatest, this routine is the same or similar.

What this routine does is traverse the 5 shells many times. Each time, it will check each shell and see if it is greater than the next shell, if it is, it will swap the two shells. This will have the effect of moving the largest numbers to the right and the smaller numbers to the left - in other words, sorting them.



Consider the first time through, looking at each shell in turn, and swapping them with the next if it is larger, would, by default, move the largest number to the end.

Lets take a look at what will happen on the first run through.

35241 (look at 1st number, swap if 3 > 5)
35241 (look at 2nd number, swap if 5 > 2)
32541 (look at 3rd number, swap if 5 > 4)
32451 (look at 4th number, swap if 5 > 1)
32415

This moved the largest number (5) to the end. This means that the next time through, we would only need to look at the first 4 numbers, and so on until there is only one number left. That will tell us that the shells are sorted. BTW: Did you notice that we only stepped throuigh the first 4 numbers? That's because the last number is, well, it's the last number and doesn't have a next number to compare to.

Another way to know if they are all sorted (after all, we don't yet know if they are in order before we start) is if we traverse the shells and none needed to be swapped. If we didn't swap any then its in order and we can stop.

Let's start. Create a new project in Delphi with a form. Drop a TMemo and a TButton on the form. We'll put all the code on the OnClick event of the button, so we can follow it easier. First declare the counters; the shells themselves; and a true/false variable to tell us that no swaps were made during the last traversal.

var
    i, LastShell: integer;
    Shell : Array[1..5] of integer;
    NoSwap: boolean;

Then we'll place a procedure inside the OnClick event (something that I would not normally do, but we're keeping it all tight for you). This procedure will simply display the current state and order of the shells so we can see what's happening.

procedure ShowShells;
var
    i: integer;
    s: string;
begin
    // display the shell order in the TMemo
    s := '';
    for i := 1 to 5 do
        s := s + IntToStr(Shell[i]);
    Memo1.lines.Add(s);
end;

Go on, say ShowShells shix times quickly. Then we'll add another procedure. This one will swap a shell with the next and tell us that the swap occured.

procedure Swap(var First, Second: integer);
var temp: integer;
begin
    Temp := First;
    First := Second;
    Second := Temp;
    NoSwap := false;
end;

Note that I declared variable parameters, but I also could have swapped the array directly. Either way would have been acceptable in this situation.

Now we can start writing code in the OnClick event itself. First we'll fill the array with the current order of the shells.

begin
    Shell[1] := 3;
    Shell[2] := 5;
    Shell[3] := 2;
    Shell[4] := 4;
    Shell[5] := 1;
    memo1.Clear;
    ShowShells;

Now we can do the actual sorting, using the counters. Remember, we are going down in the number of shells we need to sort each time (the largest will move to the end each time).

    memo1.lines.add('now sorting...');
    for LastShell := 5 downto 1 do
    begin
        NoSwap := true; // No swaps this time through yet
        // traverse the unsorted shells 
        for i := 1 to LastShell-1 do
        begin
            if Shell[i] > Shell[i+1] then
                // its greater than next, swap them
                Swap(Shell[i], Shell[i+1]);
            ShowShells;
        end;
        if NoSwap then
            // we traversed the shells and didn't need to swap
            // any therefore its sorted and we can stop.
            break;
    end;
    memo1.lines.add('Done');
end;

Note that we only traversed the shells to LastShell-1? that's because we can't look to swap the lastshell with the next one as its the last shell :-)

Here's the full code...

procedure TForm1.Button1Click(Sender: TObject);
var
    i, LastShell: integer;
    Shell : Array[1..5] of integer;
    NoSwap: boolean;

    procedure ShowShells;
    var
        i: integer;
        s: string;
    begin
      s := '';
      for i := 1 to 5 do
          s := s + IntToStr(Shell[i]);
      Memo1.lines.Add(s);
    end;

    procedure Swap(var First, Second: integer);
    var temp: integer;
    begin
        Temp := First;
        First := Second;
        Second := Temp;
        NoSwap := false;
    end;
 
begin
    // assign numbers to the array
    Shell[1] := 3;
    Shell[2] := 5;
    Shell[3] := 2;
    Shell[4] := 4;
    Shell[5] := 1;
    memo1.Clear;
    ShowShells;
    memo1.lines.add('now sorting...');
    for LastShell := 5 downto 1 do
    begin
        NoSwap := true; // No swaps this time through yet
        // traverse the unsorted shells 
        for i := 1 to LastShell-1 do
        begin
            if Shell[i] > Shell[i+1] then
                // its greater than next, swap them
                Swap(Shell[i], Shell[i+1]);
            ShowShells;
        end;
        if NoSwap then
            // we traversed the shells and didn't need to swap
            // any therefore its sorted and we can stop.
            break;
    end;
    memo1.lines.add('Done');
end;