Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
    
The important point of the topic linked by Jamal is that you should not modify your original source after answers have been posted. Even posting your new version in addition to your first version is problematic since people might not be able to notice which version an answer is referencing. –  DarkDust Sep 8 '14 at 14:18
    
@DarkDust what should I do then ? Open a new question for each modification would seem unreasonable ? What if I number my edits #1,#2 and so on and refer to my edits in my post with the representative number of edit ? –  gues532 Sep 8 '14 at 14:24
    
You could just post major revisions as a new question. Improved code should still not be appended to the question. –  Jamal Sep 8 '14 at 14:26
    
@Jamal it's said that posting an improved code is the same as answering my question, but I don't know if this can be called an improved code since I don't know if the modifications I made are ok? Anyway is it ok if I'll just copy paste everything in this question and just change the my code to the new one and post it as a new question all the time until my code will be vok? –  gues532 Sep 8 '14 at 14:30

1 Answer 1

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.

share|improve this answer
    
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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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