The Insertion Sort Algorithm

The Insertion Sort Algorithm is used by people in everyday life more than any other algorithm. If you've ever dropped a stack of papers, re-organized a bookshelf, or played cards, chances are that you've used Insertion Sort. The underlying concept of the Insertion Sort Algorithm is that elements from an unordered set should be removed one by one and then individually inserted into the correct position in an ordered set.

These are the steps taken to a set using Insertion Sort:

Elements in blue indicate comparisons.
Elements in red indicate insertions.

Ordered Set		Unordered Set
[]			[2][7][3][1][8]	--compare 2 to nothing in the ordered set
[2] 			[7][3][1][8]	--insert 2 into the empty ordered set

[2] 			[7][3][1][8]	--compare 7 to 2
[2][7] 			[3][1][8]	--insert 7 after 2 since it is larger

[2][7] 			[3][1][8]	--compare 3 to 2
[2][7] 			[3][1][8]	--compare 3 to 7
[2][3][7] 		[1][8]		--insert 3 after 2 but before 7, since 2 < 3 < 7

[2][3][7] 		[1][8] 		--compare 1 to 2
[1][2][3][7] 		[8]		--insert 1 before 2, since 1 < 2

[1][2][3][7] 		[8]		--compare 8 to 1
[1][2][3][7] 		[8]		--compare 8 to 2
[1][2][3][7] 		[8]		--compare 8 to 3
[1][2][3][7]		[8]		--compare 8 to 7

[1][2][3][7][8] 	[]		--insert 8 after 7, since 7 < 8
[1][2][3][7][8]		[]		--no more elements in the unordered set: finished sorting

From this it would seem that this is a very natural, very efficient algorithm for universal use. And indeed it is very effective in everyday life, with small physical objects. However, it is not so simple when you try to manipulate an array: the ordered and unordered sets must be partitions within the same array, and before you can insert you must first move the adjacent elements out of the way. An implementation of the algorithm is shown below:

public void insertionSort(int array[])
// pre: array is full, all elements are non-null integers
// post: the array is sorted in ascending order
{
	int temp;		// this variable is the element of the unsorted array currently
				// being compared to elements of the sorted array
	int pos;		// this variable keeps track of where in the sorted array the 
				// comparison takes place
	
	for (int i = 1; i < array.length; i++)		// loop through the unsorted array
	{
							// (the first element is considered sorted)
		temp = array[i];			// grab the first element of the unsorted array
		pos = i - 1;				// get the index of the last sorted element
		
		while ((pos >= 0) && (temp < array [pos]))	// while the current sorted element is greater than temp
		{
			array[pos + 1] = array[pos];		// keep shifting sorted elements back by 1
			pos--;					// decrement the pos index
		}
		array[pos + 1] = temp;				// insert temp such that array[pos] <= temp < array[pos + 2]
	}
}	

Written by Eugene Jitomirsky

Copyright © 2005-2016 MyCSTutorials.com