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

• gues532: I just thought of something. Won't their will work faster in some cases like when we have a large array and it's already sorted and we pass it to the function ?
• 200_success: It's true that the book's implementation is more optimized and has an O(n) best case. However, if you really cared about performance, you wouldn't use bubble sort at all.
• gues532: Yea I know there're more efficient sorting algorithms but just for learning purposes, in a high-end program what would a programmer choose if he had too between those algorithms ? One that will take less executions on more scrambled array than the other, but still the same number of executions on an already organized array or will he choose to use the other algorithm which take more executions on more scrambled array but less executions on almost organized one?
• 200_success: Programmers decide on an algorithm and implementation based on several competing factors, such as readability, speed, compactness, scalability, memory usage, and simplicity. There is no single right answer. Your algorithm and the book's have different performance characteristics. However, I feel pretty confident in saying that if you want the book's algorithm, the way I rewrote it is clearer.