Java Example – Insertion Sort Algorithm

Insertion Sort

Idea: Start at position 1 and move each element to the left until it is in the correct place
At iteration i, the leftmost i elements are in sorted order.
Sorts list by moving each element to its proper place.
Efficient for sorting small numbers.
In place sort: Takes an array A[0..n-1] (sequence of n elements) and arranges them in place, so that it is sorted.
Attempts to improve high selection sort key comparisons.

Pseudo Code

for i = 1; i < a.size(); i++

tmp = a[i]

for j = i; j > 0 && tmp < a[j–1]; j—

a[j] = a[j–1]

a[j] = tmp

In this lesson we will learn how to write a source code in Java programming language for doing simple Insertion sort using array in ascending order.

Write a program for Insertion Sort in java.

import java.util.Arrays;

/**
 * Created by ProgrammingKnowledge  .
 */

public class InsertionSort {
    public static void main (String[] args){
        int[] list = {4,3,2,5,9,6,3,21,42,4,3,6};
        System.out.println("Before Bubble sort\n");
        System.out.println(Arrays.toString(list));
        list = insertionSort(list);
        System.out.println("\nAfter Bubble sort");
        System.out.println(Arrays.toString(list));
    }
    public static int[] insertionSort(int[] list){
        if(list.length <2){
            return list;
        }
        for(int i =1; i<list.length;i++){
            int j = i-1;
            int current = list[i];
            while(j>-1 && list[j]>current){
                list[j+1] = list [j];
                j--;
            }
            list[j+1] = current;
        }
        return list;
    }
}


/**
 * Output
 Before Bubble sort

 [4, 3, 2, 5, 9, 6, 3, 21, 42, 4, 3, 6]

 After Bubble sort
 [2, 3, 3, 3, 4, 4, 5, 6, 6, 9, 21, 42]
 */