Visual Basic 2010 (Console) Guide
Insertion Sort

The insertion sort is the closest sort algorithm to the way that we might sort the array if we wrote the numbers on some cards. Imagine that this is the case. You would take the first card and place it on the table. You would then take the second card and place it to the left or right of the first one depending on whether it was greater or less than that item. When the third card is taken, if it goes at the start of the list, you would need to shuffle the other cards to the right to put it in the correct position.

The following algorithm can be used for an insertion sort,

For outerLoop = 1 To arrayLength - 1
   temp = item[outerLoop]
   innerLoop = outerLoop
   While (innerLoop > 0 And item[innerLoop - 1] >= temp)
      item[innerLoop] = item[innerLoop - 1]
      innerLoop = innerLoop - 1
   End While
   item[innerLoop] = temp
Next outerLoop

Insertion Sort Example

The following sample generates a random array of 10000 doubles. We are not concerned with looking at these values here, just the time it takes to execute the sort. The stopwatch is used here to time the execution.

Dim randomArray(10000) As Double

Sub RandomNumbers()
   Dim rand As New Random()
   For count = 0 To randomArray.Length - 1
      randomArray(count) = rand.NextDouble()
End Sub

Sub InsertionSort()
   Dim temp As Double
   Dim inner As Integer, outer As Integer
   For outer = 0 To randomArray.Length - 1
      temp = randomArray(outer)
      inner = outer
      While inner > 0 AndAlso randomArray(inner - 1) >= temp
         randomArray(inner) = randomArray(inner - 1)
         inner -= 1
      End While
      randomArray(inner) = temp
End Sub

Sub Main()
   Dim stopWatch As New Stopwatch()
   Console.WriteLine("Insertion Sort Took {0} Milliseconds", stopWatch.ElapsedMilliseconds)
End Sub

The first line of the Sub Main is used to make sure that the numbers we generate aren't the same each time.

Having A Go

  1. Change the array declaration to make it so that only 10 numbers are used. Add an additional function to round the numbers down to 2 decimal places and return a string of the whole array. Output the result to the console before and after sorting to show that the array is indeed being sorted.
  2. Adapt the program so that an identical copy of the array is made when the array is initialised. Write procedures to restore the array to unsorted state after sorting. Add the bubble sort code that you wrote using the algorithm on that page. Run the program with both sorting algorithms being used to sort the same set of unsorted data. Compare the times.