2
\$\begingroup\$

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++)
    {
        int j = i;
        while(j > 0 && arr[j] < arr[j - 1])
        {
            int swap = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = swap;
            j--;
        }
    }
}

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

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

\$\endgroup\$
  • \$\begingroup\$ Questions posted to Code Review should contain code that is working, to the best of your knowledge. \$\endgroup\$ – 200_success Sep 8 '14 at 3:02
  • \$\begingroup\$ What you can and cannot do after receiving answers. I'm rolling back your edit with the revised code and closing this question. Please ask another question if you would like to review your revised code. \$\endgroup\$ – 200_success Sep 8 '14 at 10:14
  • \$\begingroup\$ @200_success Asking the same question with a modified code is alright ? It isn't considered spam ? Also Before I do that, I wanted to ask, before I edited the code it used to work fine, yet you told me I've implemented it incorrectly, so why was it working and sorting the array ? Have I implemented other sorting technique by mistake ? \$\endgroup\$ – gues532 Sep 8 '14 at 10:48
  • \$\begingroup\$ I've verified that your code mis-sorts { 5, 4, 3, 2, 1 }. Go ahead and ask a separate question, as we have a very strict interpretation of what constitutes a duplicate question here on Code Review. However, I did give advice in my answer, which I strongly suggest that you incorporate into your code before you ask again. The more fundamental issues you have already taken care of in your code, the more insightful the answers can be. \$\endgroup\$ – 200_success Sep 8 '14 at 11:01
  • \$\begingroup\$ @200_success Yea I understand that the code should be working to the best of my my knowledge but after running multiple checks it's seems to work fine so I was certain that the code is correct, I'm sorry for this and I'll check the array example you gave me :) \$\endgroup\$ – gues532 Sep 8 '14 at 11:22
3
\$\begingroup\$

By inspection, your implementation is incorrect: arr[0] can never be written to. The only code that writes to arr is inside the while loop, and the body of the while loop will only execute when j > 0.

In addition, the style could be improved. Any code of the form

int j = …;
while (some condition involving j)
{
    …
    j--;
}

would be more easily recognizable if written as a for-loop.

The body of the inner loop looks like it performs swaps with neighbouring elements. You should be able to shift multiple elements over by one slot by doing fewer writes than that.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Why arr[0] can not be written to ? In my code, let's assume i = 1 so j = 1 as well. Now let's assume that in arr[0] we have 50 and in arr[1] we have 5, now we check if we can enter the while loop and j > 0 and also arr[1] (5) < arr[0] (50) so we enter the loop and swap arr[1] with arr[0], any chance you've misread my function correctly ? Because I'm pretty sure the function can write to arr[0]. EDIT : I think I've seen an error in my code, I'll edit my original post and tell me what you think of it now. \$\endgroup\$ – gues532 Sep 8 '14 at 9:56
  • \$\begingroup\$ Nonetheless, even with this mistake that I spotted, the algorithm sorted the array with no problems before which I found it weird, I've run multiple checks and each time it sorted the algorithm with no problem (even with the mistake) \$\endgroup\$ – gues532 Sep 8 '14 at 10:03

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