Comparing two bubble sort algorithms

Question

I'm learning C and I've got to a point learning about different sorting algorithms. Before seeing how it was done, I wanted to try doing it myself based on what I read on how it's working.

int temp;
    for(int i = 0; i < SIZE - 1; i++)
    {
        for(int j = 0; j < SIZE - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }

This is what the code from where I learn looks like:

for(int i = 0; i < SIZE; i++)
{
       if((i < SIZE - 1) && (arr[i] > arr[i+1]))
       {
                  int tmp = arr[i];
                  arr[i] = arr[i + 1];
                  arr[i + 1] = tmp;
                  i = -1;
       }
}

Now, obviously they're different, but is one more efficient in someway than the other? Did I do something that is less efficient than their code?

Answer 1

Your implementation

Your implementation is mostly pretty good. I'd just make a few minor changes:

• int temp should be declared in the tightest scope possible — namely, inside the if block. Localizing the variable further makes it harder to misuse and easier to understand. I'd also rename temp to swap to make its purpose clearer. (Naming a variable temp is usually a bad idea, in my opinion.)
• int temp is at the wrong level of indentation. Maybe you just made an error when pasting the code here?
• There is a space after if, but not after for. Be consistent. I recommend putting the space there to distinguish those keywords from function calls.

• The j < SIZE - 1 - i condition is a bit hard to follow. You could apply the transformation ii = SIZE - 1 - i, and have the outer loop count backwards instead.

  for (int ii = SIZE - 1; ii > 0; ii--)
  {
      /* Let the largest element bubble up to the end */
      for (int j = 0; j < ii; j++)
      {
          if (arr[j] > arr[j + 1])
          {
              int swap = arr[j + 1];
              arr[j + 1] = arr[j];
              arr[j] = swap;
          }
      }
  }
  

Answer 2

The book's implementation

Normally, asking for a review of code written by others is off-topic for Code Review. However, given the simplicity of the code, the context of your question (requesting a comparison with your own working implementation), and the fact that it's a book that you're learning from, I feel compelled to comment.

I think that your version is much better! Your book seems to be promoting some questionable programming practices.

• Inconsistent whitespace: The indentation widths are not the same. Also, the if condition has arr[i+1], which is written as arr[i + 1] in the statements below.
• Misleading for loop: The loop header makes it look like a simple loop in which i is incremented by i with each iteration. That's a lie! In fact, i gets reset to -1 whenever a swap occurs. What looks like a simple algorithm that makes one linear pass through the array is actually an O(SIZE²) algorithm.
• Magic number: What is the significance of -1? It's a roundabout way to reset i to 0, once the i++ in the loop's epilogue is taken into account.
• Weird loop limit: The last iteration through the loop, when i = SIZE - 1, is guaranteed to have no effect, since if ((i < SIZE - 1) && …) will always fail.

A less deceptive way to express the book's algorithm would be:

    int i;
    do
    {
        for (i = 0; i < SIZE - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                int swap = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = swap;
                break;  /* Start over at i = 0 */
            }
        }
    } while (i < SIZE - 1);