Insertion Sort[Java Implementation]

                                        Insertion Sort

Insertion Sort is a sorting technique to sort the elements which can be easily implemented and is more efficient than Selection Sort and Bubble Sort .It is efficient for small data sets.But,Merge Sort and Quick Sort is better. Tim Sort is best technique to sort the elements.Insertion sort is easy to implement.For more information:-

http://en.wikipedia.org/wiki/Insertion_sort

Time Complexity of Insertion Sort:-

Best            =>       O(n)

Average      =>       O(n^2)

Worst          =>       O(n^2)  

Example:-

Sort => 4 3 2 1

Step 1.  We take the 2nd element as key i.e.

                  key=3

          Now check till if any no.is greater than key then place it on next place(or position) i.e

                  4  4  2  1 

          Now all the elements are checked place key at the  index+1 where index is the first smallest no. is found.

                  3 4 2  1

Now same steps as considering the keys further.

Step 2.

       3  4   2  1

       3  4   4  1

       3  3   4  1

       2  3   4  1

Step 3.

       2  3  4   1

       2  3   4  4

       2  3   3  4

       2  2   3  4

       1  2   3  4

We get the sorted set of elements.

Program:-

/**

 * @(#)InsertSort.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/5/2

 */

import java.io.*;

class InsertSort {

    public static void main(String args[])throws IOException{

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    System.out.println("Enter the no. of Elemeents to be sorted:");

    int n=Integer.parseInt(br.readLine());

    int ar[]=new int[n];

    String inp[]=br.readLine().split(" ");

    for(int i=0;i<n;i++){

    ar[i]=Integer.parseInt(inp[i]);

    }

    ar=InsertSort(ar);

    for(int i=0;i<n;i++){

    System.out.print(ar[i]+" ");

    }

   

    }

    

    public static int[] InsertSort(int ar[]){

   

    int key,j;

   

    for(int i=1;i<ar.length;i++){

   

    key=ar[i];

    j=i-1;

   

    while(j>=0&&ar[j]>key){

    ar[j+1]=ar[j];

    j--;

    }

   

    ar[j+1]=key;

    }

   

    return ar;

    }

    

    

}

Output:-

Enter the no. of Elemeents to be sorted:

5

2 1 10 5 3

1 2 3 5 10 

--------------X--------------X--------------X--------------X--------------X--------------X-----------