Previous questions:

  1. Is my implementation of insertion sort is correct?
  2. Sorting an int[] array with an Insertion Sort

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 is my implementation:

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

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.

  • In terms of the algorithm, I would say that it is now an insertion sort, so that is good. As a Java guy, I will stay away from reviewing the implementation though. – rolfl Sep 8 '14 at 15:38
up vote 1 down vote accepted

Nice job. It looks like you have implemented a correct insertion sort.

The inner loop could be better written: the j > 0 condition is giving an incomplete picture of how the loop terminates.

One other change you should make is to take a size parameter for the array size. Without it, you have a function that only works on arrays of a specific size! If you look at examples of functions in the C library, almost every function that takes an array also takes another parameter to specify its size. Usually, the type of that parameter is an unsigned int, but called size_t to make its purpose clear.

#include <stdlib.h>

void insertionSort(int arr[], size_t size)
{
    for (int i = 1; i < size; i++)
    {
        int value = arr[i];
        int j;
        /* Shift elements over by one slot to make way for the insertion */
        for (j = i; j > 0 && value < arr[j - 1]; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = value;
    }
}

Your implementation is better than the book you're learning from. In fact, I would recommend using a different book, if the code examples are so poor. Specifically, the biggest problem is the done flag. Setting a flag to be inspected by a conditional elsewhere is a cumbersome way to implement flow control. Your break is much more direct and assertive, and I think that my loop condition is even clearer.

  • Oh yea I could just add the if to the for condition, thanks. By the way, I see a lot of examples that use names for variables / data structures with names such as xxx_t, what is the t representing ? – gues532 Sep 8 '14 at 17:26
  • …_t is a POSIX convention for types. Use them, but don't define any …_t of your own. – 200_success Sep 8 '14 at 17:29
  • You're welcome. Please remember to upvote all answers that you find helpful on the site (as well as any questions that you find interesting). – 200_success Sep 8 '14 at 17:30

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.