Insertion Sort Working Java Program Code with Example

Sorting is  to place elements in increasing or decreasing order.  Insertion sort  is a simple sorting algorithm .
In this sorting algorithm , the final sorted array can be build one at a time .For larger data , when compared to other sorting techniques  like quick sort , heap sort  or merge sort ,it falls short .

Read Also :      Bubble Sort Java Code with Example

When to Use

Insertion sort is good to use for small number of input elements(less than 1000) . You can see  by running the below algorithm for
(Input)(Space)                           (Time taken)
10 elements           :           Insertion sort took   0  milliseconds
100 elements         :           Insertion sort took   0  milliseconds

1000 elements       :           Insertion sort took   0  milliseconds 

10000 elements     :           Insertion sort took    1 milliseconds
100000 elements   :           Insertion sort took    3 milliseconds


So , you can see it is not wise decision to use Insertion sort for large number of elements as other algorithms take much less time .

Read Also  :       Selection Sort in Java


Big O Notation

In simple words , Big O allows us to say something about how the size of inputs affect the runtime of a program .This technique can also be applied to other resources that an algorithm takes up (such as memory)
and we can analyze other bounds than the upper bound such as lower bound on time or space or expected time or space that an algorithm takes up .

Properties

* It is a  Stable algorithm i.e does not change the relative order of elements with equal keys
* Very low overhead
* Online i.e can sort a list as it receives it

Best , Average,Worst Cases

*  Best Case        :    O(n)
* Average Case   :    O(n^2)
* Worst Case      :    O(n^2)


Read Also :      Merge Sort in simple words with Example

                         Quick Sort Java Code with Example


Demo here :

The code is given below :

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;

public class InsertionSort {
    
    
    public static int[] insertionSort(int[] list) {
        for (int i = 1; i < list.length; i++) {
            int next = list[i];
            // find the insertion location while moving all larger element up
            int j = i;
            while (j > 0 && list[j - 1] > next) {
                list[j] = list[j - 1];
                j--;
            }
            // insert the element
            list[j] = next;
        }
        return list;
    }
    
    
    
    public static void main(String args[]) throws Exception
    {
        String list="";
        int i=0,n=0;
        
        InsertionSort s= new InsertionSort();
        ArrayList<Integer> arrlist=new ArrayList<Integer>();
        System.out.println(" ");
        System.out.println(" ");
        System.out.println("Please enter the list of elements,one element per line");
        System.out.println(" write 'STOP' when list is completed ");
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        while(!(list=bf.readLine()).equalsIgnoreCase("stop")){
            int intelement=Integer.parseInt(list);
            arrlist.add(intelement);
            
        }
        
        int elementlist[]  = new int[arrlist.size()];
        Iterator<Integer> iter = arrlist.iterator();
        for (int j=0;iter.hasNext();j++) {
            elementlist[j] = iter.next();
        }
        
        elementlist=insertionSort(elementlist);
        System.out.println(" ");
        System.out.println(" ");
        System.out.println(" ");
        System.out.println("Values after Insertion Sort : ");
        for (int j=0;j<elementlist.length;j++) {
            System.out.println(elementlist[j]+" ");
        }
    }
}