 Java Tutorial

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, array, ... 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");
}
}
}
```
Output:
```\$ 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
```     