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
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. You will need to add another using statement for the code to work,
using System.Diagnostics;
There are ways to make the timing more accurate than we are doing here, but we can get an idea.
static double[] randomArray = new Double[10000];
static void RandomNumbers()
{
Random randomNumber = new Random();
for (int i = 0; i < randomArray.GetLength(0); i++)
{
randomArray[i] = randomNumber.NextDouble();
}
}
static void InsertionSort()
{
double temp;
int inner;
for (int outer = 0; outer < randomArray.GetLength(0); outer++)
{
temp = randomArray[outer];
inner = outer;
while (inner > 0 && (randomArray[inner - 1] >= temp))
{
randomArray[inner] = randomArray[inner - 1];
inner -= 1;
}
randomArray[inner] = temp;
}
}
static void Main(string[] args)
{
RandomNumbers();
Console.WriteLine("Number of Items: {0}", randomArray.GetLength(0));
Stopwatch sWatch = new Stopwatch();
sWatch.Reset();
sWatch.Start();
InsertionSort();
sWatch.Stop();
Console.WriteLine("Insertion Sort Completed: {0} milliseconds",sWatch.ElapsedMilliseconds);
Console.ReadLine();
}