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

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.