Insertion Sort Program in Java

Java Program on Insertion Sort Algorithm

In the last posts, We have learned some sorting algorithm like bubble sort algorithm and selection sort algorithm. Now here we are going to discuss another sorting algorithm which is insertion sort algorithm. Here we will see insertion sort program in java.

Let's start insertion sort algorithm java programs step-by-step.

What is insertion sort algorithm?

Java insertion sort algorithm is easy and simple algorithm like bubble sort algorithm. By the help of insertion sort we can easily sort any array elements. Insertion sort algorithm builds the final sorted array or list one item at a time.

Java insertion sort repeatedly takes the next element from the un-sorted section of an array and insert it into the sorted section at the right position.

Initially, insertion sort takes first element as a sorted element and then take the second element and compare it with first element and if the second element is less than first element then swap two number that means the second element comes to first and first comes to the second position in an array. Again compare the third element with second and again swap number and so on ...... until get sorted array.

Advantage of insertion sort

• Insertion sort algorithm is simple algorithm in java like bubble sort.

• Insertion sort is stable in nature i.e insertion sort does not change the relative order of an elements with equal keys.

Disadvantage of insertion sort

There are one draw back of insertion sort is it is not suitable for large data set. It is suitable only small data set.

Time complexity of insertion sort algorithm

• worst case: O(n^2)
• average case: O(n^2)
• best case: O(n^2)
• worst case space complexity: O(1)

Here is your  insertion sort code java program using for loop and while loop.

Insertion Sort Example

This is simple example of insertion sort in java sorting algorithm. Where we will sort array elements by inserting un-sorted elements at correct position.

public class InsertionSortDemo

{

public static int[] insertionSort(int array[])

{
int temp;

for(int i = 1; i < array.length; i++)

{

for(int j = i; j > 0; j--)

{

if(array[j] < array[j - 1])

{

       temp = array[j];

       array[j] = array[j - 1];

       array[j - 1] = temp;

     }

  }

}

      return array;

}

static void displayArray(int inputarray[])

{

for(int i : inputarray)

{

System.out.print(i);

System.out.print(",");

}

System.out.println();

}

public static void main(String args[])

{

int array[] = {5,15,20,9,1,7,27};

System.out.println("before sorting elements");

displayArray(array);

int array1[] = insertionSort(array);

System.out.println("after sorting elements");

displayArray(array);

}

}

Output: before sorting elements
             5,15,20,9,1,7,27,
             after sorting elements
             1,5,7,9,15,20,27,

All the java sorting algorithm e.g bubble sort, merge sort, selection sort, insertion sort, quick sort are quite important for java written and oral interviews.

In the next post, We will learn another important java sorting algorithm e.g merge sort algorithm a quick sort algorithm with example.

I hope above example of java insertion sort program will be useful to you. This is useful article for core java interviews like other sorting programs.