Insertion Sort Simplified



Click here for a larger image.

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();
}

Downloads

Download demo project - 5 Kb
Download source - 568 Bytes


Comments

  • 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:
    theory.lcs.mit.edu/~prahladh/6046/rec4.ps

    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

      Reply
    Reply
  • 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.

    Reply
  • 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

    Reply
  • 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
    your software! :)
    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.

    Reply
  • 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...

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: September 19, 2014 @ 2:00 p.m. ET / 11:00 a.m. PT In response to the rising number of data breaches and the regulatory and legal impact that can occur as a result of these incidents, leading analysts at Forrester Research have developed five important design principles that will help security professionals reduce their attack surface and mitigate vulnerabilities. Check out this upcoming eSeminar and join Chris Sherman of Forrester Research to learn how to deal with the influx of new device …

  • Adaptation and evolution are fundamental requirements of survival -- not only in nature, but also in business. Our world has changed dramatically in a short amount of time. Many businesses are fueling and capitalizing on this change, while others are desperately clinging to a bygone era. Who is left standing in the years and decades ahead should come as no surprise. This edition of Unleashing IT highlights the companies that are embracing new circumstances, new methods, and new opportunities. By downloading …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds