Visual C# 2005 Guide
Shell Sort

The shell sort was invented by Donald Shell (honestly). It is an improvement on the insertion sort. When you look at each line of output as the insertion sort is executed, you can see that items are exchanged with adjacent items. This means that the larger the distance between an item and its sorted location, the longer it will take to be placed in the right location. The shell sort improves upon this by comparing more distant items. An algorithm for the shell sort is shown below. The variable h represents the distance between the compared items on each pass.

The shell sort is the quickest algorithm of those shown so far, particularly as the number of items increases. There are quicker methods for sorting, but they get more and more complicated to program.

h = 1
While (h<=arrayLength/3)
   h = h * 3 +1
End While
While (h > 0)
   For outerLoop = h To arrayLength - 1
      temp = item[outerLoop]
      innerLoop = outerLoop
      While (innerLoop > h - 1 And item[innerLoop - h] >= temp)
         item[innerLoop] = item[innerLoop - h]
         innerLoop = innerLoop - h
      End While
      item[innerLoop] = temp
   Next outerLoop
   h = (h - 1)/3
End While

Shell Sort Procedure

static void ShellSort()
{
   int h = 1;
   int inner;
   double temp;
   while (h <= randomArray.GetLength(0) / 3)
   {
      h = h * 3 + 1;
   }
   while (h > 0)
   {
      for (int outer = h; outer < randomArray.GetLength(0); outer++)
      {
         temp = randomArray[outer];
         inner = outer;
         while (inner > h - 1 && randomArray[inner - h] >= temp)
         {
            randomArray[inner] = randomArray[inner - h];
            inner -= h;
         }
         randomArray[inner] = temp;
      }
      h = (h - 1) / 3;
   }
}

Having A Go

  1. Add this algorithm to your program and compare the execution time of all of the sorting methods covered so far.