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

## Be First to Comment