Wednesday 15 August 2007

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;

15 comments:

  1. Apologies to everyone - it seems that either my explorer is not clearing memory, or the posting is not adjusting as I want. I will have to clean up that code tonight.

    There should be 4 space indents and blank lines between the procedures. If you can see that, then its my cache that's causing the problem. I'll recheck the display tonight.

    ReplyDelete
  2. I'm sure that seashells are a romantic way to remember this algorithm, but isn't it called the Shell Sort simply because the inventor was Donald Shell?

    ReplyDelete
  3. thanks Anthony, and apologies to Donald Shell. I was always taught the sea shell way as an easy way of knowing what happens in the routine.

    I stand corrected.

    Steve

    ReplyDelete
  4. This is just an optimized bubble sort, not a shell sort.

    check:

    http://en.wikipedia.org/wiki/Shell_sort

    I think the differences will become immediately apparent.

    ReplyDelete
  5. As stated in the blog "...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..."

    ReplyDelete
  6. I presume you are directing this mostly at newbies so you need to add that this type of sort is only better than quicksort when you are sorting what is mostly in order, like when you resort a list after making an addition. It's worst case performance would be when the list is in reverse order like when you click a column heading in a list to reverse the sort.

    ReplyDelete
  7. This isn't anything like a shell sort, and is in fact EXACTLY the very model an optimized bubble sort, which is no more a shell sort than Delphi is C with artistic license.

    ReplyDelete
  8. Thanks to you both for your comments. As there are several sorting routines available within Delphi, the newbie can choose the best suited for their use. This was only to let them know what happens behind the scenes.

    To the last poster. I have answered this statement already.

    ReplyDelete
  9. Just to add a little to what was stated by Anonymous above (regarding performance against other sorting routines).

    I agree with the poster. You should choose your sorting routines for the job on hand. I would not think it necessary to use the code I placed here in any of your programs - it was placed as way of understanding what goes on behind the scenes of a simple sorting routine. By all means, load it into Delphi and have a play with it, changing it as you see fit, but you don't need to use it in real life as Delphi has a number of sorting routines that are available to you. TStringList for example has its own sort.

    ReplyDelete
  10. That is exactly why you can't trust anything you see in the internet.I recommend you put a gigantic sign saying "This ain't Shell Sort!", so ppl won't just do like I did and spend a day thinking this is a shell sort when it's not. I now have to start my work all over again because of this blog.

    ReplyDelete
  11. He he, this is exactly why people should read the "gigantic sign" that says this is not a "Shellsort".

    ReplyDelete
  12. Hey, me again (last poster). I now see what you were trying to do, seems like you made up a sort (which is not new). Nothing wrong with that, ok. But to name it exactly the same as an older one, with a space in between, that's just wrong. And I can't even be sure if the original one was with or without space, since you'll find references to the same sort either way you look for it. Except here.
    And the fact that you laugh about it is disturbing for me.

    ReplyDelete
  13. I was not laughing at the Shell Sort, I was laughing at your not seeing the statement right at the top that already did exactly what you had asked of me (sort of a LOL or Smiley face, not a derogatory laugh).

    You will note from the early comments that I named the post incorrectly, my bad (you might even read an apology in that). However since you seem not to read but are instead, very keen on criticism then you are most welcome to go ahead and be disturbed.

    If you do care to read, then you might just find a very sweet little optimised bubble sort put in such highly visual and memorable way of the swapping shells that is a favorite of the swift of hand.

    ReplyDelete
  14. Sorry if I sounded too critical, frustration does that sometimes, but it's al good now. I actually enjoyed your sort, because it was well explained, but I really think the name was a problem. Well, they say every knowledge you gather can only do you good, so it's ok.

    ReplyDelete
  15. The explanation is very good.but for what shell sort is used i.e. is there any practical implementation for shell sort.....

    ReplyDelete

Note: only a member of this blog may post a comment.