# Visual Basic 2010 (Console) GuideInsertion 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()    Next 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    Next End Sub Sub Main()    Randomize()    RandomNumbers()    Dim stopWatch As New Stopwatch()    stopWatch.Reset()    stopWatch.Start()    InsertionSort()    stopWatch.Stop()    Console.WriteLine("Insertion Sort Took {0} Milliseconds", stopWatch.ElapsedMilliseconds)    Console.ReadLine() 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.