Algorithms – Sorting – Insertion Sort

Insertion sort is considered as one of simplest of all the sorting algorithms. The strategy behind insertion sort is to pick up an element from the list and place it at the right position in the list at the end of each iteration.

Algorithm:

//Input: An array of elements to be sorted denoted by ‘A’ and the size of the array denoted by ‘n’

//Output: In-place sorted array

//Requirement: The contents of the array to be sorted should be comparable with each other i.e. it is expected that relational operations can be applied on the contents of the array.

procedure insertionSort (A, n)
for i = 1 to n-1 do
input (A, i, A[i])
done
end

 

procedure insert (A, pos, value)
i = pos-1
while (i>=0 && A[i]>value) do
if (A[i]>A[i+1]) then
swap A[i] and A[i+1]
i=i-1
endif
done
swap A[i+1] and value
end

 


Source Code snippet for the above Algorithm in C++:

/* Few assumptions:
* There exists a class named Sort that contains utility methods along
* with sorting methods. The utility methods take care of reading the
* input into an array named 'input' and a variable titled
* 'elementCount' represents the total number of elements in an array.
*/

template<typename elementType>
void Sort<elementType>::insertionSort() {
for (int i = 1; i <= elementCount - 1; i++) {
// For all elements starting from position 1 not 0.
insert(input, i, input[i]);
}
}

// Insertion Sort helper function
template<typename elementType>
void Sort<elementType>::insert(elementType input[], int pos, elementType value) {
int i = pos - 1;
// Shift all the element that are greater than the current element under
// consideration to the right by 1 position.
while (i >= 0 && *(input + i) > value) {
*(input + i + 1) = *(input + i);
i -= 1;
}
// Insert the current element at the right position.
*(input + i + 1) = value;
}

Reference:

  • Book: Introduction to the Design and Analysis of Algorithms by Anany Levitin. Copyright 2003, 0-201-74395-7.
  • Book: Algorithms in a Nutshell by George T. Heineman, Gary Pollice, and Stanley Selkow. Copyright 2009 George Heineman, Gary Pollice, and Stanley Selkow, 978-0-596-51624-6.
  • Wikipedia: http://en.wikipedia.org/wiki/Insertion_sort
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s