Insertion Sort

In this artcle we are going to learn about insertion sort algorithm and insertion sort implementation in java.

Insertion sort:-

In insertion sort the array is divided into two parts first part is sorted and second part is unsorted. To start with sorted array will have only first element in sorted array and the all remaining element will be in unsorted array. The array having only one element is sorted by itself . Now take the second element and compare it with the first element. If the second element is smaller than the first element then swap first and second element. Now after first iteration the sorted array contain first two element and unsorted array contains remaining elements. Now take the third element and compare with second element. if the third element is smaller than the second element and so on.

Now the array will scan untill the following situation will occur Array[0]<Array[1]<——–Array[N].

Insertion sort algorithm:-

1. Set i=1.
2. Repeat step 3 to 9. while(i<size of array).
3. set j = i-1.
4. set Temp = Array[i].
5. Repeat step 6 & 7 while(j>0 and Temp <= A[j].
6. set A[j+1] = A[j].
7. set A[j] = temp.
8. set j = j-1.
9. set i = i+1.
10. Exit.

Insertion sort n java:-

package learn;
import java.util.*;
public class insertionSort {

	public static void main(String[] args) {

Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of array");
  int n = sc.nextInt();
  int[]a = new int[n];
  System.out.println("Enter the array");
  for(int i=0;i<n;i++)
     {
	  a[i] = sc.nextInt();
	 }
   insertionSort(a);
   System.out.println("Array after sorting");
   for(int i=0;i<a.length;i++)
   {
	   System.out.println(a[i]);
   }
	}
 
	public static void insertionSort(int[]a) {
	 int temp = 0;
	 for(int i=1;i<a.length;i++) 
	 {
		temp = a[i]; 
		for(int j=i-1;j>=0 && temp<a[j];j--) 
		{
			a[j+1] = a[j];
			a[j] = temp;
		}
		
		
	  }
  }

}

Output:-

We can also implement insertion sort in other programming languages like C, C++, Python, etc.