what is insertion sort?
Insertion sort is one of the techniques available for re-arrangement of given input variables. The efficiency of this techinique decreases with the increase in the size of the input data. That is insertion sort is advisable only if the size of the data is limited. To sort data of higher size, there are advanced techniques which can sort them with better efficiency. One of the basic sorting technique is Bubble sort.

For every single iteration in insertion sort, single element will be sorted to it’s final position in the array. Single element will be considered for every iteration and compared with before element in the array.

Let us consider, input data be 3 4 1. Insertion sort starts with 1st element of the array(If you are numbering it from 0) or starts for 2nd element of the array(If you are numbering it from 1) and will be regarded as key element of that particular iteration. Here the key element for 1st iteration is 4 and the key element will be compared with the predecessor elements of the array. If the predecessor is greater than key, then sort two elements. If predecessor is not greater than key, leave it intact. In the next round of iteration the key element will be 1 and it will be compared with 4. Since predecessor is greater than 1, those two elements are sorted and again 1 will be compared with 3. 1 and 3 are sorted and the entire array is sorted.

Insertion Sort in C

import java.io.*;
import java.util.*;

public class insertion{
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int i,j,temp;

		System.out.print("\n Enter size of the array: ");
		int size = in.nextInt();

		int[] data = new int[size];
		for(i=0;i<size;i++){
			System.out.print("\n Enter data into the array: ");
			data[i] =  in.nextInt();
        }

        for(i=1;i<size;i++){
        	j=i;
        	while(j>0 && data[j-1] > data[j]){
        		temp = data[j-1];
        		data[j-1] = data[j];
        		data[j] = temp;
        		j--;
        	}
        }

        System.out.println("\n\tSorted data is:\n");
        for(i=0;i<size;i++){
        	System.out.print("\t"+data[i]);
        }
	}
}

Output:

Download the source code