Insertion Sort Program in Java with Explanation

Write a program to implement insertion sort algorithm in java.  How insertion sort is different from bubble sort and selection sort.

Insertion sort is a simple sorting algorithm. It works by inserting each element at the proper place in a sorted list.

Insertion sort explanation.

Java programs

Insertion Sort Program in Java

package insertionsort;

import java.util.*;

public class Insertionsort {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
          int n;
          
          System.out.println("Enter the number of element in an array");
          
          Scanner in = new Scanner(System.in);
          n = in.nextInt();
          
          int[] arr = new int[n];
          
          System.out.println("Enter unsorted values in an array");
          
          int i, j ,k;
          
          /* Taking unsorted values from user */
          
          for (i = 0 ; i < n; i++) {
              
              arr[i] = in.nextInt();
              
          }
          
          /* Sorting values using insertion sort */
          
          for ( i = 1; i < n; i++) {
              
              k = arr[i];
              
              for (j = i - 1; j >= 0 && k < arr[j]; j-- ) {
                  
                    arr[j+1] = arr[j];
              }
              
              arr[j+1] = k;
          }
          
          System.out.println ("After sorting an array");
          
          for (j = 0; j < n; j++) {
              
              System.out.print(arr[j]+" ");
          }
    }
    
}

Output -

Enter the number of element in an array  :  4

Enter unsorted values in an array :

12
5
9
2

After sorting an array :

2     5      9      12


Explanation


Suppose we have input following values.

12   5   9    2

Step 1 -  12 is compared with 5 and position is swapped.

 After step 1 -    5   12  9   2

Step 2 - 9 is compared with 5 and 12 and position is swapped.

After step 2 -   5    9    12    2

Step 3 - 2 is compared with 5, 9 and 12 and position is swapped.

After step 3 -   2    5    9    12


You can also create separate method for insertion sort and sort the unsorted array. Here is the code snippet for sorting.

public static void insertionSort(int[] A){

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

            int value = A[i];
            int j = i - 1;

            while(j >= 0 && A[j] > value){

                A[j + 1] = A[j];
                j = j - 1;

            }

            A[j + 1] = value;

        }

        /* Assume this is the method which prints 
           the final sorted array */

        printArray(A);
    }