Visual Basic 2010 (Console) 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

Sub ShellSort()
   Dim h As Integer = 1
   Dim inner As Integer
   Dim temp As Double
   While h < randomArray.Length / 3
      h = h * 3 + 1
   End While
   While h > 0
      For outer = h To randomArray.Length - 1
         temp = randomArray(outer)
         inner = outer
         While inner > h - 1 AndAlso randomArray(inner - h) >= temp
            randomArray(inner) = randomArray(inner - h)
            inner -= h
         End While
         randomArray(inner) = temp
      Next
      h = (h - 1) / 3
   End While
End Sub

Having A Go

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