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
- Add this algorithm to your program and compare the execution time of all of the sorting methods covered so far.