Practical difference between two Bubble Sort loops

Question

I have been told by my Teacher that this is is the one and only code for Bubble Sort:

int a[] = {2, 3, 7, 9, 8, 1, 4, 5, 10, 6};
for (int i = 0; i < a.length; i++) {
    for (int j = 0; j < a.length - i - 1; j++) {
        if (a[j] > a[j + 1]) {
            int t = a[j];
            a[j] = a[j + 1];
            a[j + 1] = t;
        }
    }
}
for (int i = 0; i < a.length; i++) {
    System.out.print(a[i] + "\t");
}

But I ran the program with a different outer loop:

int b[] = {2, 3, 7, 9, 8, 1, 4, 5, 10, 6};
for (int i = 0; i < b.length - 1; i++) {
    for (int j = 0; j < b.length - i - 1; j++) {
        if (b[j] > b[j + 1]) {
            int t = b[j];
            b[j] = b[j + 1];
            b[j + 1] = t;
        }
    }
}
for (int i = 0; i < b.length; i++) {
    System.out.print(b[i] + "\t");
}

The Outputs are:

1st Case:

1   2   3   4   5   6   7   8   9   10

2nd case:

1   2   3   4   5   6   7   8   9   10

So now I am being told that my code is wrong, even if my output comes correct.

Please, tell me am I entirely wrong??

Answer 1

Both versions will sort correctly. However the 1st version will always do an extra (unneccessary) pass, since its doing N passes, while if one thinks about it, the maximum times an element may change places, is N-1 (that would be when the smallest/largest number is at the wrong end of the array).

So 2nd version is a little more effective, it reduces complexity from approximately O(N*N) to O(N*(N-1)). Which is largely the same.

So, your teacher should recognize your code is correct. Since teachers are often stuck in their thinking model, be diplomatic about it when you talk to him, and carefully lead him to the conclusion above that N-1 outer passes are enough.

Answer 2

This is the beginning of a known optimisation of bubble sort: http://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort

Answer 3

Your outer loop doesn't iterate over all elements. Check out b.length-1 for(int i=0;i<b.length-1;i++). That means, that if you have 10 elements you will iterate until 8th element. Since you are using both < and length-1. If you want to stick with .length-1. You should change condition to i<=b.length-1.