Insertion Sort

 

Sample Input 1:

5
4 3 8 2 9

Sample Output 1:

Sorted Array -> 
2 3 4 8 9 

import java.util.Scanner;

public class InsertionSort {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n=s.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++)
		{
			a[i]=s.nextInt();
		}
		
		insertionSort(a);
		print(a);

	}
	
	public static void print(int a[])
	{
		System.out.println("Sorted Array -> ");
		for(int i=0;i<a.length;i++)
		{
			System.out.print(a[i]+" ");
		}

	}
	 public static void insertionSort(int[] arr) {
		 
		 int l=arr.length;
		 //Considering 0th element will be in sorted
		 for(int i=1;i<l;i++)
		 {
			 int j=i-1;
			 int t=arr[i];
			 while(j>=0 && arr[j]>t)
			 {
				 arr[j+1]=arr[j];
				 j--;
			 }
			 arr[j+1]=t;
		 }

}
}