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
- Given an unsorted array and let length denotes number of elements in an array.
- We will use two loops to sort an array.
- 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.
- Once we are out of loop, we will get sorted array.
Performance analysis of insertion sort algorithm
S. No. | Cases | Complexity |
---|---|---|
1 | Best case | O(n) |
2 | Average case | O(n^2) |
3 | Worst case | O(n^2) |
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 ] |