C# Insertion Sort

Your task is to write a method called InsertionSort, which takes an array of integers and sorts them into ascending order:

public static void InsertionSort(int[] array)

Do not use Array.Sort or other predefined sorting methods that are part of the .NET framework to implement this method. This method should be written from scratch.

The pseudocode is reproduced here for your convenience:

sorted length is 1 // list of single element is already sorted
while sorted length < length of list
let newItem = first element of unsorted part

// insert newItem in its correct position by
// moving all the items greater than newItem up one position

let currentPos = start of unsorted part
while currentPos > 0 and item at currentPos-1 > newItem
move the item at currentPos-1 up one position
decrement currentPos
end while

// insert newItem in the “vacant” position
item at currentPos = newItem
increment sorted length
end while

If the pseudocode is confusing read the rest of the lecture slides about Insertion Sort first, to ensure you have a good grasp of the algorithm before you attempt to start implementing it.

The provided Main() method contains a simple test for your InsertionSort(), and should produce the following output:

Note that the Main() method of the provided code is never called- only the InsertionSort() method is called in order to test your program. This also means your InsertionSort() method must be public.

If you still have difficulties, here are some tips when writing programs for AMS:

Do not write your program directly into the text box. You should copy and paste the sample code into Visual Studio, write your program there, run it and test it to make sure it works, then paste it into AMS. You only get a limited number of attempts at each AMS exercise, so make sure they count.

Sample code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace InsertionSort
{
class Program
{
public static void InsertionSort(int[] array)
{
// Write your insertion sort algorithm here
}
static void Main(string[] args)
{
int[] array = { 1, 2, 6, 3, 4 };
InsertionSort(array);
for (int i = 0; i < array.Length; i++)
{
if (i > 0) {
Console.Write(", ");
}
Console.Write("{0}", array[i]);
}
Console.WriteLine("nnPress enter to exit.");
Console.ReadLine();
}
}
}