Software & Finance





Java - Insertion Sort





We often using sorting algorithm to sort numbers and strings. Also we have many sorting algorithms. I have explained here on how insertion sort algorithm works using Java programming Language. Look at the yellow color high lighting section on output to understand how algorithm works after each iteration.

Click here for Java BubbleSort Algorithm

Click here for Java InsertionSort Algorithm

Click here for Java MergeSort Recursive Algorithm

Click here for Java MergeSort Iterative Algorithm

Click here for Java QuickSort Recursive Algorithm

Click here for Java QuickSort Iterative Algorithm


The complete program and test run output are given below:

 

Source Code


import java.io.*;

 

 

class InsertionSort {

 

     

 

    public static void main(String[] args) {

 

            String inpstring = "";

            InputStreamReader input = new InputStreamReader(System.in);

            BufferedReader reader = new BufferedReader(input);

 

            try

            {

                  System.out.print("Enter a Number Elements for INSERTION SORT:");

                  inpstring = reader.readLine();

 

                  long max = Long.parseLong(inpstring);

                  long[] arrElements = new long[100];

                  for (int i = 0; i < max; i++)

                  {

                        System.out.print("Enter [" + (i + 1) + "] Element: ");

                        inpstring = reader.readLine();

                        arrElements[i] = Long.parseLong(inpstring);

                  }

                 

 

                  for(int i = 1; i < max; i++)

                  {

                        int j = i;

                        while(j > 0)

                        {

                              if(arrElements[j-1] > arrElements[j])

                              {

                                    long temp = arrElements[j - 1];

                                    arrElements[j - 1] = arrElements[j];

                                    arrElements[j] = temp;

                                    j--;

                              }

                              else

                                    break;

                        }

      

                        System.out.print("After iteration " + i + ": ");

                        for(int k = 0; k < max; k++)

                              System.out.print(arrElements[k] + " ");

 

                        System.out.println("/*** " + i + " numbers from the begining of the array are input and they are sorted ***/");

                  }

 

 

                  System.out.println("The numbers in ascending orders are given below:");

                  for (int i = 0; i < max; i++)

                  {

                        System.out.println(arrElements[i]);

                  }

 

            }

            catch (Exception e)

            {

                  e.printStackTrace();

            }

    }

}

 

Output


C:\Java\Samples>javac InsertionSort.java

 

C:\Java\Samples>java InsertionSort

Program for Ascending order of Numeric Values using INSERTION SORT

 

Enter the total number of elements: 8

 

Enter [1] element: 80

Enter [2] element: 60

Enter [3] element: 40

Enter [4] element: 20

Enter [5] element: 10

Enter [6] element: 30

Enter [7] element: 50

Enter [8] element: 70

 

Before Sorting   : 80 60 40 20 10 30 50 70

After iteration 1: 60 80 40 20 10 30 50 70

After iteration 2: 40 60 80 20 10 30 50 70

After iteration 3: 20 40 60 80 10 30 50 70

After iteration 4: 10 20 40 60 80 30 50 70

After iteration 5: 10 20 30 40 60 80 50 70

After iteration 6: 10 20 30 40 50 60 80 70

After iteration 7: 10 20 30 40 50 60 70 80

 

 

The numbers in ascending orders are given below:

 

Sorted [1] element: 10

Sorted [2] element: 20

Sorted [3] element: 30

Sorted [4] element: 40

Sorted [5] element: 50

Sorted [6] element: 60

Sorted [7] element: 70

Sorted [8] element: 80