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 ]