Twitter
An insertion sort is another example of a simple sorting algorithm. Insertion sort is based on the methodology that given a list of unsorted elements, we take and element and insert it into it’s proper position. By doing this for every element in the unsorted list, we will finally have a sorted list.
Insertion sort
Insertion sort is an in place sorting algorithm and does not need any extra memory space during the sorting procedure. The algorithm implemented below considers whether an element is less than the elements before it, if so we shift all the elements which are greater than it by one position. We insert the element when we find it’s proper position.
Insertion sort has a runtime complexity of O(n²) in it’s worst case similar to bubble sort but it has the advantage of being an incremental sort. What this means is that if the list is already sorted, a new element can be inserted into the list with a runtime complexity of O(n). So it can work great in something like a dropdown list which is already sorted and we add a new element.
int insertion_sort(int array[], const int size)
{
int i,j;
int key;
for(i=1; i < size; i++)
{
key = array[i];
j = i - 1;
while((j >= 0) && (key < array[j]))
{
array[j+1] = array[j];
j--;
}
array[j+1] = key;
}
return 0;
}
Related Posts:
Tags: programs
It’s a shame Insertion Sort doesn’t get taught as an introduction to sorting algorithms instead of Bubble Sort. I’ve implemented both in a variety of languages and Insertion Sort takes about half the time.
[Reply]
Kevin Reply:
January 13th, 2010 at 3:39 pm
Yes, you are quite right. Insertion sort performs much better than bubble sort and is also quite simple to understand. Perhaps both should be taught with their differences and understanding of their complexity.
[Reply]