This is in C#. Your task is to write a method called InsertionSort, which takes

Question

This is in C#.

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:

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:

1, 2, 3, 4, 6

Press enter to exit.

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.

Please use the sample code below in your answer:

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(" Press enter to exit.");
Console.ReadLine();
}
}
}

Explanation / Answer

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)
        {

            // list of single element is already sorted
            int sortedLen = 1;
            //while sorted length < length of list
            while (sortedLen < array.Length)
            {
                //let newItem = first element of unsorted part
                int newItem = array[sortedLen];

                //let currentPos = start of unsorted part
                int currentPos = sortedLen;

                //while currentPos > 0 and item at currentPos-1 > newItem
                while (currentPos > 0 && array[currentPos-1] > newItem)
                {
                    //move the item at currentPos-1 up one position
                    array[currentPos] = array[currentPos - 1];

                    //decrement currentPos
                    currentPos--;
                }
                // insert newItem in the “vacant” position
                //item at currentPos = newItem
                array[currentPos] = newItem;
                // increment sorted length
                sortedLen++;
            }
        }
        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(" Press enter to exit.");
            Console.ReadLine();
        }
    }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.