Java Program for Insertion Sorting

What is insertion sort ?

One element from the list of elements is consumed in each iteration to find its correct position.

i'th iteration we "insert" the i'th element array[i] into it's correct position among array[1], array[2], ... array[i-1] which were previously placed in sorted order.

Insertion Sorting Steps

Insertion Sorting Time complexity

Insertion sorting time complexity is O(N^2). here N is the number of elements in the list.

Insertion Sorting Java Program

This java program is used to sort the array of integers using insertion sorting technique.

import java.util.Scanner;

public class InsertionSortingTest {
	
    public static void insertionSort(int[] listVals){
    	int numberOfElements = listVals.length;
    	for(int i=0;i<numberOfElements;i++){
	        // temp stores current element whose left side is traversed              
	        // to find correct position
    		int temp = listVals[i];
    		int j = i;
	        // checks whether left side elements are less than current element.
	        while(j > 0 && temp < listVals[j-1]){                                
	            listVals[j] = listVals[j-1];                                  
	            j = j - 1;              
	        }                                                                                
	        // moving current element to correct position in left side.              
	        listVals[j] = temp;  
    	}
    }

	public static void main(String[] args){
		int[] numberList;
		Scanner in = new Scanner(System.in); 
		System.out.println("Insertion Sorting");
		System.out.println("--------------------");
	    System.out.println("Enter numbers count: ");                   
	    int count = in.nextInt();                   
	    numberList = new int[count];
	    System.out.println("Enter numbers: "); 
	    for (int i=0;i<count;i++){
	    	numberList[i]=in.nextInt();
	    }
	    in.close();
	    insertionSort(numberList);
	    
	    System.out.println("Sorted numbers: "); 
	    for(int number : numberList){
	    	System.out.print(number+"\t");
	    }
	}
}                                                                                                                                            

$ javac InsertionSortingTest.java
$java InsertionSortingTest 
Insertion Sorting
--------------------
Enter numbers count: 
5
Enter numbers: 
25
18
19
35
16
Sorted numbers: 
16	18	19	25	35