I'm currently learning about different sorting algorithms and after reading on the concept of the insertion sort of how it's done I've tried to implement it by myself before seeing how it was implemented in the source from which I'm learning.

This was my implementation:

void insertionSort(int arr[])
{
    for(int i = 1; i < SIZE; i++)
    {
        for(int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
        {
            int swap = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = swap;
        }
    }
}

Now I think I've implemented it correctly (not talking about efficient or anything just the algorithm itself), but when I saw the way it was implemented in the course I'm seeing I had a bit of concerns about my implementation because they're really different and I just wanted to make sure my implementation is really an insertion sort algorithm implementation and I didn't done anything else.

Here's the implementation by the source I'm learning from:

void insertionSort(int arr[])
{
  for(int i = 1;, i < SIZE; i++)
  {
      int value = arr[i];
      int j = i - 1;
      int done = 0;
      do
      {
          if (arr[j] > value)
          {
              arr[j + 1] = arr[j];
              j--;
              if (j < 0)
                  done = 1;
          }
          else
          {
              done = 1;
          }
      } while(!done)
      arr[j + 1] = value;
  }
}

Is my implementation of insertion sort correct ?

Also I would appreciate if you could compare my implementation to the one made by the source I'm learning from, any efficiency differences or any other thing you think would worth mentioning.

up vote 3 down vote accepted

Your implementation is not quite correct. It is subtle, but what you have is a type of bubble sort in that you do not insert the new value, rather you 'slide' the value in to place.

An insertion sort can be thought of as a 'hole'. You shift all the 'bigger' values to the right by one space, and create a hole at the point where the value should be inserted. Then you insert the value in to the hole.

There should not be a concept of a 'swap' in an insertion sort.

You start at the first unsorted value, and then if the previous values are smaller, you move them up one, until you have the space at the right spot. Then you put the value there.

The example code makes this 'obvious' (but not really), in that it always compares against value and not arr[j+1]. It also has only a single 'assignment' to the array for each time in the loop. Your swap routine does two assignments on each loop.

So, No, your implementation of an insertion sort is not quite correct. It is a correct sort, but not a 'text-book' insertion sort since it slides, rather than inserts the value.

  • I think I understand what you mean, so instead of sliding it we insert it ONLY when we find it's correct position so we're doing less swapping. Could you correct me if I'm wrong? – gues532 Sep 8 '14 at 14:06
  • @gues532 - you are not wrong. Sort algorithms differ in small ways, and, in this instance, that small difference is significant in that it is what defines it as an insertion sort. Sort of like saying I have this 'blue' car, only it is a 'green' car. – rolfl Sep 8 '14 at 15:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.