Insertion sort algorithm in java programming

• Sorting means arranging elements of a array or list in ascending or descending order.
• We have various sorting algorithms in java.


• Iterative and recursive algorithms.
• Insertion sort is iterative type of algorithm.
• Insertion sort algorithm is in place algorithm
• The basic idea behind insertion sort is to divide our list in to two parts , sorted and un sorted.
• At each step of algorithm a number is moved from un sorted part to sorted part.
• Initially take 1st element as sorted element. 
• Noe take second element and compare with first element if it less than the 1st element then swap two numbers means place lesser value in first position.
• So now have two elements in sorted part. Take third element and compare with second element if it is less than the second element then we need to compare it with 1st element if is less than first element we need keep that in first place. Take an element  from unsorted portion and compare with sorted portion and place it in correct position in order to make sorted.
• This will be repeated until entire list will be sorted.

Time complexity of Insertion sort:

1.Best case  time complexity:      O(n²)
2.Average case time complexity: O(n²)
3.Worst case time complexity:     O (n²)
4.Worst case space complexity:  O(1)


Implementation of Insertion sort algorithm in java

Program #1: Write a java example program on insertion sort algorithm.

1. package com.instanceofjava.insertionsortalgorithm;
2. 
   
3. public class InsertionSort {
4. 
   
5. /**
6. * @website: www.instanceofjava.com
7. * @category: insertion sort algorithm in java
8. */
10.      
11. public static int[] doInsertionSort(int[] array){
12.          
13.      int temp;
14.  
15.   for (int i = 1; i < array.length; i++) {
16.  
17.             for(int j = i ; j > 0 ; j--){
18.                 if(array[j] < array[j-1]){
19.                     temp = array[j];
20.                     array[j] = array[j-1];
21.                     array[j-1] = temp;
22.                 }
23.             }
24.  
25.        }
26.         return array;
27.  }
28.  
29.   static void printArray(int[] inputarray){
30.  
31.     for(int i:inputarray){
32.              System.out.print(i);
33.              System.out.print(", ");
34.          }
35.     System.out.println();
36.   }
37.     
38.  public static void main(String a[]){
39.    
40.    int[] array = {16,12,3,11,9,21,5,6};
41.  
42.     System.out.println("Before sorting elements");
43.     printArray(array);
44.  
45.     int[] resarray = doInsertionSort(array);
46.  
47.     System.out.println("After sorting elements");
48.     printArray(array);
49.        
50. }
51. }

Output:

1. Before sorting elements
2. 16, 12, 3, 11, 9, 21, 5, 6, 
3. After sorting elements
4. 3, 5, 6, 9, 11, 12, 16, 21,