Insertion Sorting Algorithm in C#

Insertion sort is an elementary sorting algorithm that sorts one element at a time. The algorithm takes an element from the list and places it in the correct location in the list. This process is repeated until there are no more unsorted items in the list. The computational complexity for insertion sort is O(n2).

Algorithm: Insertion Sort

It works the way you might sort a hand of playing cards:

We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].
Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].
To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

Pseudocode

We use a procedure INSERTION_SORT. It takes as parameters an array A[1.. n] and the length n of the array. The array A is sorted in place: the numbers are rearranged within the array, with mostly a constant number outside the array at any time.

INSERTION_SORT (A)

FOR j ← 2 TO length[A]
DO key ← A[j]
{Put A[j] into the sorted sequence A[1 . . j − 1]}
i ← j − 1
WHILE i > 0 and A[i] > key
DO A[i +1] ← A[i]
i ← i − 1
A[i + 1] ← key

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace InsertionSort
{
class Program
{
static int InsertionSorting()
{
Console.Write("\nProgram for sorting a numeric array using Insertion Sorting");
Console.Write("\n\nEnter number of elements: ");
int max = Convert.ToInt32(Console.ReadLine());
int[] numarray = new int[max];
for (int i = 0; i < max; i++)
{
Console.Write("\nEnter [" + (i + 1).ToString() + "] element: ");
numarray[i] = Convert.ToInt32(Console.ReadLine());
}
Console.Write("Input int array : ");
for (int k = 0; k < max; k++)
Console.Write(numarray[k] + " ");
Console.Write("\n");
for (int i = 1; i < max; i++)
{
int j = i;
while (j > 0)
{
if (numarray[j - 1] > numarray[j])
{
int temp = numarray[j - 1];
numarray[j - 1] = numarray[j];
numarray[j] = temp;
j--;
}
else
break;
}
Console.Write("Iteration " + i.ToString() + ": ");
for (int k = 0; k < max; k++)
Console.Write(numarray[k] + " ");
Console.Write("\n");
//Console.Write("/*** " + (i + 1).ToString() + " numbers from the begining of the array are input and they are sorted ***/\n");
}
Console.Write("\n\nThe numbers in ascending orders are given below:\n\n");
for (int i = 0; i < max; i++)
{
Console.Write("Sorted [" + (i + 1).ToString() + "] element: ");
Console.Write(numarray[i]);
Console.Write("\n");
}
return 0;
}
static void Main(string[] args)
{
InsertionSorting();
Console.ReadLine();
}
}
}

1 Comment

Join the conversation! Your thoughts help the community grow.

Nilesh Jadav10y ago
So far it is the best code ! Can you make this sorted output in desending form ? And can you check comparison between both ascending and descending with the help of count ? Can you help me with this code : http://www.c-sharpcorner.com/forums/worst-case-of-insertion-sort-in-c-sharp