What is Insertion Sort? Write a java program to demonstrate it?

Introduction

The insertion sort technique is similar to sorting playing cards in our hands. We pick a card and place it in the sort order. When we complete this process with all the cards the array will be sorted.

A sample array sorting is shown in the below picture:

 

Java Program

import java.util.InputMismatchException;
import java.util.Scanner;

public class InsertionSort {
 public static void main(String[] args) {
 int n , handIndex;
 Scanner input = null;
 int[] a = null;
 try {
 input=new Scanner(System.in);
 System.out.println("Enter size of the array:");
 n= input.nextInt();

 if(n > 0) {
 a=new int[n];
 System.out.println("Enter array elements:");
 for (int i = 0; i < n; i++) {
 a[i] = input.nextInt();
 }
 }else{
 System.out.println("Enter positive number.");
 System.exit(0);
 }

 System.out.println("Input Array:");
 printArray(a);
 for(int i =0 ; i<a.length; i++)
 insertionSort(a,i+1) ;

 System.out.println("Sorted Array:");
 printArray(a);
 }catch (InputMismatchException ime) {
 System.out.println("Not a valid input");
 }
 catch (Exception e) {
 e.printStackTrace();
 } finally
 {
 if(input!=null)
 {input.close();}
 }
 }

 private static void printArray(int[] a){
 for (int aA : a) {
 System.out.print("[ " + aA + " ]");
 }
 System.out.println( "");
 }

 private static void insertionSort(int[] a, int card){
 for(int j=1; j< card; j++){
 int key = a[j];
 int k = j-1;
 while(k >=0 && key < a[k])
 {
 a[k+1] = a[k];
 --k;
 }
 a[k+1] = key;
 }

 for(int hand=0; hand< card; hand++){
 System.out.print("[h " + a[hand] + " h]");
 }
 System.out.println( "");
 }


}

 

The run output of the program

Enter size of the array:
5
Enter array elements:
23
56
9
103
77
Input Array:
[ 23 ][ 56 ][ 9 ][ 103 ][ 77 ]
[h 23 h]
[h 23 h][h 56 h]
[h 9 h][h 23 h][h 56 h]
[h 9 h][h 23 h][h 56 h][h 103 h]
[h 9 h][h 23 h][h 56 h][h 77 h][h 103 h]
Sorted Array:
[ 9 ][ 23 ][ 56 ][ 77 ][ 103 ]