Insertion Sort

Overview

Insertion Sort is a very simple sorting algorithm which builds a sorted array a single item at a time. It can be said that Insertion Sort is not an efficient implementation when dealing with large data sets and is much slower than more advanced algorithms such as Merge Sort, Quicksort, or Heapsort.

Concept

The idea behind Insertion Sort is simple to understand. Insertion Sort iterates over the input array (or list) and removes one element each time through and finds the location it belongs within the sorted list and inserts it there.

Algorithmic Complexity

Big-O

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Insertion SortArrayO(n)O(n^2)O(n^2)O(1)

 

Implementation

Java Implementation


import java.util.Arrays;

/**
 * Insertion Sort algorithm implementation
 * 
 * www.algorithmiccomplexity.com
 */
public class InsertionSort {
	
	public static int[] insertionSort(int[] unsortedArray)
	{
		for(int i = 1; i < unsortedArray.length; i++)
		{
			int temp = unsortedArray[i];
			
			int j;
			
			for(j = i - 1; j >= 0 && temp < unsortedArray[j]; j--)
			{
				unsortedArray[j+1] = unsortedArray[j];
			}
			
			unsortedArray[j+1] = temp;
		}
		
		return unsortedArray;
	}
	
	/**
	 * Test driver for the insertion sort algorithm.
	 * 
	 * @param args Command line arguments {@code null}.
	 */
	public static void main(String[] args)
	{
		int[] unsortedArray = new int[9];
		unsortedArray[0] = 10;
		unsortedArray[1] = 5;
		unsortedArray[2] = 3;
		unsortedArray[3] = 7;
		unsortedArray[4] = 1;
		unsortedArray[5] = 8;
		unsortedArray[6] = 8;
		unsortedArray[7] = 0;
		unsortedArray[8] = 6;
		
		System.out.println(Arrays.toString(unsortedArray));
		unsortedArray = InsertionSort.insertionSort(unsortedArray);
		System.out.println(Arrays.toString(unsortedArray));
	}
}

References

Wikipedia: Insertion sort

 

<- back