Insertion Sort- Algorithm and Coding Examples

Insertion sort is a frequently used sorting technique to sort a small count of elements since its complexity is O(n^2). It gets the name insertion sort because of the way sorting is accomplished. Elements are picked one by one from left to right. All bigger elements before the selected are moved backwards by one position to make a hole for the element selected.

In every pass one element is thus inserted at its correct position. That means that the insertion of this element is done in the subset of the array that is already sorted.

Algorithm Insertion Sort

Algorithm InsertionSort(DATA, N)
Description: This algorithm sorts the array named DATA storing N elements by moving and inserting one element at a time in the partially sorted array in each pass.
1.	Initialize K=1
2.	Repeat steps 3 to 9 while K<N
3.	TEMP= DATA[k] 	[store current element in TEMP to later interchange with element at correct position of kth element]
4.	J=K-1
5.	Repeat steps 6 to 7 while (TEMP<DATA[J]) and J>=0 [find an element that is just smaller than the current element while moving each bigger element one position backwards to make a hole of current element in the partially sorted array]
6.	DATA[J+1]=DATA[J]   [Move the element backwards]
7.	J=J-1 [Decrement J to pick next bigger element before the current element whose correct place is to be found]
8.	DATA[J]=TEMP [ Copy the current element TEMP at its correct position in the sorted array]
9.	K=K+1   [Increment K to pick next current element]
10.	Exit

In each pass the elements from first index and one less than the current index of the pass are sorted. The current element is stored in TEMP variable and is compared with all elements before it that are in sorted order. If the current element index is 5, then 5^th element is compared with elements from 4 to 0^th till an element less than current element is located.

In every comparison the elements bigger than the current element are moved one position backward. Search ends when an element less than current element is found and value of TEMP is stored at the index next to this smaller element.

If you have played a game of cards you can relate to it. When cards are given to you, first you make a hand out of the cards you get. Every card is from right is inserted towards left by finding its correct position in increasing order and all the higher and unsorted cards are shifted towards right. Every new card is inserted in this way to maintain the order of cards for quick extraction of card when your turn comes.

Code solutions –Insertion Sort

Code in C

#include<stdio.h>
#include<conio.h>
int main()
{
//declare variables	
int data[100],n,k,i,j,temp;
//Input size of Data array
printf("How many elements you want to sort? : ");
scanf("%d",&n);
//Input the array elements
printf("Input arry elements: ");
for(i=0;i<=n-1;i++)
{
	scanf("%d",&data[i]);
}
//browse through the array to insert the elements at correct position
for(k=1;k<=n-1;k++)
{
	//store the element to be sorted in temp
	temp=data[k];
	//initialise counter variable with index of previous element
	j=k-1;
	//find the correct loczton of kth element 
	while((temp<data[j])&&(j>=0))
	{
		//move the current element one position backward
		data[j+1]=data[j];
		//get index of previous element
		j=j-1;
	}
	//place kth element at its found location to be inserted
	data[j+1]=temp;
}
//Print sorted elements
printf("Sorted elements are are :\n");
for(i=0;i<n;i++)
{
	printf("%d\n",data[i]);
}
}

Java Code

The input given in this program is by using the command line input

import java.io.*; 

public class insort
{
		void Sort(int data[], int n)
		{
		//declare variables	
		int k,i,j,temp;
		//browse through the array to insert the elements at correct position
		for(k=1;k<n;k++)
		{
			//store the element to be sorted in temp
			temp=data[k];
			//initialise counter variable with index of previous element
			j=k-1;
			//find the correct loczton of kth element 
			while((temp<data[j]))
			{
				//move the current element one position backward
				data[j+1]=data[j];
				//get index of previous element
				j=j-1;
				if (j<0)
					break;
			}
			//place kth element at its found location to be inserted
			data[j+1]=temp;
		}
		}
		void display(int[] data, int n)
		{
			int i;
			//Print sorted elements
			System.out.println("Sorted elements are:\n");
			for(i=0;i<n;i++)
			{
				System.out.println(data[i]);
			}
		}
		public static void main(String args[]) 
		{ 
			int i;
			// data will be read from command line. create data array of size equal to count of values inputted by user
			int[] data= new int[args.length + 1];
			// store string values inputted by user at command line into  integer data array  
			for(i=0;i<args.length;i++)
				data[i]= Integer.parseInt(args[i]);
			insort tt =new insort();
			tt.Sort(data,data.length);
			tt.display(data,data.length);
		}
}

Python Code

def insort(data,n):
    k=1
    j=0
    
    #browse through the array to insert the elements at correct position
    while (k<n):
        #store the element to be sorted in temp
        temp=data[k]
	#initialise counter variable with index of previous element
        j=k-1
	#find the correct loczton of kth element
        while(temp<data[j]):
	    #move the current element one position backward
            data[j+1]=data[j]
	    #get index of previous element
            j=j-1
            if (j<0):
                break
            #place kth element at its found location to be inserted
        data[j+1]=temp
        print(data) 
        k=k+1
       
    return data            
        
def readarr(data):
    i=0
    n=int(input("Count of elements to sort??--->"))
    while i<n:
        data.append(int(input("input value--->")))
        i=i+1
    return n

def disparr(data,n):
    i=0
    while (i<n):
        print(arr[i])
        i=i+1
        

arr=[]
n=0
n=readarr(arr)
sarr= insort(arr,n)
print("Sorted elements are--->")
i=0
while (i<n):
    print(sarr[i])
    i=i+1

admin