Visual C# 2005 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 Sample

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();
}

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.