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 ]