# Insertion Sort Simplified

### WEBINAR:On-Demand

Application Security Testing: An Integral Part of DevOps

Environment: This code might be specific to some environments, but the concept of the sorting remains the same.

### Fundamental Concept

Approximately ten kinds of sorting methods are available, namely Heap, Quick, Merge, Insertion, Shell, Selection, Bubble, Linear, Address Selection, and Radix sort. Recently, when I was trying to go through the coding of an Insertion sort, I searched the Internet for the same and fortunately found some resources (U.S. universities), where the desired code was explained. I found the code a bit cumbersome to keep track of and difficult to understand (also debug), so I prepared myself for writing my own.

Prior to explaining the code, I will discuss the technique that is being applied to sort an array by using the Insertion sort method. As the name implies, the Insertion sort works on the insertion rule. In simpler terms: a number (at a current position in the array) is being compared with each of the array elements, from the begining of the list (array) until the current position. If the number is found to be less than the one already present, the element is transferred from its original position to this (new) position. That's all, folks.

To fully understand the concept, I have created an example. Let us assume that we have an array of 10 numbers (all positive integers); in other words, 10, 9, 1, 8, 3, 7, 4, 6, 5, and 2. According to the condition explained earlier, the number 9 should be compared with 10. Because the number 9 is less than 10, we will perform a transfer operation for 9. Here comes an important step. Placing a number at the begining of the list (or somewhere else) will cause all the elements (right from the newly found location) to shift one position right. Hence, special care has been taken in the coding to perform the desired job. When we are to make a transfer, first we store the element at its current position in a temporary variable, so that when the entire list is shuffuled the element is not lost. This methodology is followed during the entire sort operation.

Thus, we see that, after the first step, our intermediatary output becomes 9, 10, 1, 8, 3, 7, 4, 6, 5, and 2. Similarly, we can trace out the entire sequence as follows:

After Iteration 1 -  9, 10,  1,  8,  3,  7,  4,  6,  5,  2
After Iteration 2 -  1,  9, 10,  8,  3,  7,  4,  6,  5,  2
After Iteration 3 -  1,  8,  9, 10,  3,  7,  4,  6,  5,  2
After Iteration 4 -  1,  3,  8,  9, 10,  7,  4,  6,  5,  2
After Iteration 5 -  1,  3,  7,  8,  9, 10,  4,  6,  5,  2
After Iteration 6 -  1,  3,  4,  7,  8,  9, 10,  6,  5,  2
After Iteration 7 -  1,  3,  4,  6,  7,  8,  9, 10,  5,  2
After Iteration 8 -  1,  3,  4,  5,  6,  7,  8,  9, 10,  2
After Iteration 9 -  1,  2,  3,  4,  5,  6,  7,  8,  9, 10

In the preceding sequence of operations, numbers shown with bold and underlined formatting indicates the element transferred in that iteration. A point to be noticed here is that we require 9 iterations (in total) to sort an array of 10 elements. Thus, we can generalize this result as: We require (N-1) iterations to sort an array of N elements. The time complexity of this sorting method is the order of N2; in other words, O(N2). Though I am very well aware of the time-complexity factor, I don't know, for the Insertion sort, how it comes to be N2. Well, this was all about the Insertion sort method. This sorting method is not the most efficient and you must use Heap, Quick, or Merge sort, the time complexity (for the average and best case) of which are NLog2N. Below, you will find the code written in C. In the coding (though it is self explainatory), the k variable denotes the position found for the current element in the array.

### Source Code

#include <stdio.h>
#include <conio.h>
#define MAX 20

main()
{
static int arr[MAX];
int n, temp, pos;
int i, j, k;

printf("Enter the number of elements : ");
scanf("%d", &n);

printf("Enter the elements now :\n");
fflush(stdin);
for (i = 0; i < n; i++)
scanf("%d", &arr[i]);

i = 0;
pos = 0;
for (i = 0; i < n; i = (pos + 1))
{
j = pos + 1;

/* find out the jth element's appropriate position */
for (k = 0; arr[j] > arr[k] && (k < j); k++);

/* shift the list elements if the element's position is
* found */
if (k < j)
{
temp = arr[j];
pos = j;

printf("\nk = %d", k);

for (; j >= k; j--)
arr[j] = arr[j - 1];

arr[k] = temp;

printf("\tIntermediate o/p is : ");
for (i = 0; i < n; i++)
printf("%2d ", arr[i]);
}
}

printf("\n\nInsertion sorted list is : \n");
for (i = 0; i < n; i++)
printf("%d ", arr[i]);

getch();
}

• #### Who would use Insertion Sort?

Posted by Legacy on 02/22/2004 12:00am

Originally posted by: Jeffrey Walton

Take a look at bucket sort:

Bucket Sort uses insertion sort...yeah

• #### Insertion Sort works pretty well

Posted by Ecuador -=[NM]=- on 05/01/2004 07:08am

Before I ever read this article, I wrote a sort engine based on this technique, and compared to other sort engines ( bubble sort, quick sort ) I yielded quite good ( and first of all pretty fast ) results. I will post my engine ( written on Power++ (Optima) ) if anyone is interested. Unfortunately I am on vacation while I write this, so please be patient :) Greets Ecuador

• #### Insertion sorting

Posted by Legacy on 02/06/2003 12:00am

Originally posted by: Luca Piccarreta

The complexity of the algorithm is O(N^2)
because for every insertion you averagely make
N comparisons (well, I'd guess N/4) and N exhanges.
Much of the code on the internet is cumbersome,
but please do not ever put this kind of code in
Use STL
std::sort(arraypointer,arraypointer+size)
which, you said that, is QuickSort and *is* faster.
Every sorting algorithm has its advantages, like
locality, number of comparisons, number of exchanges...
but Insert Sort has none, as far as I know.
bye!
Luca.

• #### Let me clarify first.

Posted by Legacy on 02/06/2003 12:00am

Originally posted by: Krishna

Dear Luca and Peter,
Thank you very much for posting your valuable comments. I must clarify you the same that my sole purpose of writing this article was to introduce the visitors, the concept of Insertion Sort. I kept the article as simple as possible. I myself know that the other sorting algorithms are much more efficient than the one I have shown in my article, but again I have mentioned that this (Insertion Sort) is not the most efficient algorithm.

Besides this, if you really did not like the article, simply switch over to another page. ;)

Regards,
Krishna Kumar Khatri
Jaipur, India.

• #### A note to Peter

Posted by Legacy on 02/06/2003 12:00am

Originally posted by: Anand Balaji

Ya Peter,
why don't you demonstrate your programming skills? What are you currently coding... DOOM 4? LOL

• #### stupid article

Posted by Legacy on 02/05/2003 12:00am

Originally posted by: Peter

This is the most utterly useless, totally ridiculous article
written by some ignorant person...The article has no depth.

If you are stupid, you dont need to let the entire world know about it...

• You must have javascript enabled in order to post comments.

## Top White Papers and Webcasts

• As all sorts of data becomes available for storage, analysis and retrieval - so called 'Big Data' - there are potentially huge benefits, but equally huge challenges...
• The agile organization needs knowledge to act on, quickly and effectively. Though many organizations are clamouring for "Big Data", not nearly as many know what to do with it...
• Cloud-based integration solutions can be confusing. Adding to the confusion are the multiple ways IT departments can deliver such integration...

## Most Popular Programming Stories

• There have been no articles posted today.