Sorting an int[] array with an Insertion Sort

Question

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.

Answer 1

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.