# 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.