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