# 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 5th element is compared with elements from 4 to 0th 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,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

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