INSERTION SORT

Insertion sort

Insertion sort is based on the idea that one element from the input elements is consumed in each iteration to find its correct position i.e., the position to which it belongs in a sorted array.

It iterates the input elements by growing the sorted array at each iteration. It compares the current element with the largest value in the sorted array. If the current element is greater, then it leaves the element in its place and moves on to the next element else it finds its correct position in the sorted array and moves it to that position. This is done by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead.

Take array A[]=[7,4,5,2].

Since 7 is the first element has no other element to be compared with, it remains at its position. Now when on moving towards 4, 7 is the largest element in the sorted list and greater than 4. So, move 4 to its correct position i.e. before 7. Similarly with 5, as 7 (largest element in the sorted list) is greater than 5, we will move 5 to its correct position. Finally for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2 and then 2 is placed in the first position. Finally, the given array will result in a sorted array.

Time Complexity:

In worst case,each element is compared with all the other elements in the sorted array. For N elements, there will be N2 comparisons. Therefore, the time complexity is O(N²).

Program for INSERTION SORT

import java.util.Scanner;
class insertionsort
 {
  public static void main(String[] args)
  {
   int i,j,n,temp=0;
   Scanner is = new Scanner(System.in);
   System.out.println("Enter Size Of Array :");
   n=is.nextInt();
   int[] a;//declaration of array
   a=new int[n]; // Creation of array with given size
   System.out.println("Enter unsorted Array :");
   for(i=0;i<n;i++)
    {     System.out.printf("\n Element a[%d]  :",i);
     a[i]=is.nextInt();
    }
   System.out.print("\n Unsorted Array elements :");
   for(i=0;i<n;i++)
     {
      System.out.print( a[i] +" ");
     }

   for(i=0;i<n;i++)
    {
     System.out.printf("\n ADDRESS=%h ---- ARRAY=a[%d]----- DATA=%d --- location=%d\n",i*4,i,a[i],i+1);
    }

   for(j=0;j<n;j++)
    {
     temp=a[j];
     for(i=j-1;i>=0 && temp<a[i];i--)
       {
        a[i+1]=a[i];
       }
     a[i+1]=temp;
     System.out.printf("\n pass %d element inserted in proper place %d\n\n ",j,temp);
     for(i=0;i<n;i++)
     {
      System.out.print( a[i] +" ");
     }

    }
   System.out.print("\n Sorted Array elements :");
   for(i=0;i<n;i++)
     {
      System.out.print( a[i] +" ");
     }

   for(i=0;i<n;i++)
    {
     System.out.printf("\n ADDRESS=%h ---- ARRAY=a[%d]----- DATA=%d --- location=%d\n",i*4,i,a[i],i+1);
    }
  }
}

output: