Sort an integer array using insertion sort algorithm in java (with example)

What is insertion sort algorithm?

• Insertion sort is a sorting technique.
• The elements are inserted at an appropriate place in an array, so that array remains the sorted.
• The insertion sort is quite simple algorithm.
• The time complexity of insertion sort algorithm is O(n^2).
• The logical flow of insertion sort is as follows
  • Given an unsorted array in java.
  • Array will be virtually divided into two halves.
    • Sorted array and unsorted array.
    • Initially sorted array will have one element (Element at index 0) and unsorted array (from 1 to length -1).
  • We will pick element from an unsorted array, let’s say dataToBeInserted
    • We will compare dataToBeInserted with each element in a sorted array
    • dataToBeInserted will be inserted in sorted array, so that array remains sorted.
  • After every iteration, data starts moving from unsorted array to sorted array.
    • Once all the elements moved to sorted array, insertion sort completes

Properties of insertion sort algorithm

• Efficient for (quite) small data sets, much like other quadratic sorting algorithms
• More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort
• Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(nk) when each element in the input is no more than k places away from its sorted position
• Stable; i.e., does not change the relative order of elements with equal keys
• In-place; i.e., only requires a constant amount O(1) of additional memory space
• Online; i.e., can sort a list as it receives it

Algorithm: sort an array using insertion sort in java

1. Given an unsorted array and let length denotes number of elements in an array.
2. We will use two loops to sort an array.
3. Start iterating through the array
   • Outer loop iterate from 1 to length – 1 and let it be iArray.
   • Get the current element at iArray index (Let it be dataToBeInserted)
   • Assume elements on the left of iArray as sorted
     • Index of iSortedArray = iArray -1
     • iSortedArray signify the sorted Array
   • Start another lopp, to insert a element to a sorted array
     • Iterate through sorted array (iSortedArray index)
     • Compare dataToBeInserted with each element in a sorted array
       • Find and create a space, where element should be inserted.
   • Insert the element at index calculated earlier.
4. Once we are out of loop, we will get sorted array.

Performance analysis of insertion sort algorithm

Program – sort  an integer array using insertion sort algorithm in java

package org.learn.arrays;

import java.util.Arrays;

public class InsertionSort {

 public static void main(String[] args) {
  int[] example1 = { 10, 7, 25, 20, 12, 9 };
  System.out.println("Unsorted array is : " + Arrays.toString(example1));
  insertionSort(example1);

  int[] example2 = { 5, 4, 3, 2, 1, 0 };
  System.out.println("\nUnsorted array is : " + Arrays.toString(example2));
  insertionSort(example2);
 }

 private static void insertionSort(int[] inputArray) {
  
  int length = inputArray.length;
  int iArray = 1, iSortedArray, dataToBeInserted;
  
  //Start iterating the array from 1 to length
  while (iArray < length) { 
   iSortedArray = iArray - 1; dataToBeInserted = inputArray[iArray]; 
   
   //Perform insertion sort in this while loop  
   while (iSortedArray >= 0 && dataToBeInserted < inputArray[iSortedArray]) {
    //Create a space  in input array by shifting elements on right
    inputArray[iSortedArray + 1] = inputArray[iSortedArray];
    iSortedArray--;
   }
   
   //Put the element in space created by above while loop
   inputArray[iSortedArray + 1] = dataToBeInserted;
   iArray++;
  }
  
  System.out.println("Sorted Array is :"+ Arrays.toString(inputArray));
 }
}

Output – sort an integer array using insertion sort algorithm in java

Unsorted array is : [10, 7, 25, 20, 12, 9]
Sorted Array is   : [7, 9, 10, 12, 20, 25]

Unsorted array is : [5, 4, 3, 2, 1, 0]
Sorted Array is   : [0, 1, 2, 3, 4, 5]