Practical Difference Between Two Bubble Sort Loops

Question

My Teacher told me that this 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 started the program with a different external circuit -

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

Exits - 1st case -

 1 2 3 4 5 6 7 8 9 10 

The second case is

 1 2 3 4 5 6 7 8 9 10 

So, now they tell me that my code is wrong, even if my output came correctly. Please tell me that I am completely wrong?

Answer 1

Both versions will sort correctly. However, the 1st version will always perform an additional (optional) pass, since it performs N passes, and if someone thinks about it, the maximum time when an element can change is N-1 (this would be when the smallest / the largest number is at the wrong end of the array).

So, the second version is a bit more efficient, it reduces complexity from about O (N * N) to O (N * (N-1)). This is much the same.

So, your teacher should find out that your code is correct. Since teachers are often stuck in their thinking patterns, be diplomatic in this when you are talking to him and carefully bring him to the conclusion above that the external passages of N-1 are sufficient.

Answer 2

This is the start of the well-known bubble sort optimization: http://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort

Answer 3

Your outer loop does not iterate over all elements. Check b.length-1 for(int i=0;i<b.length-1;i++) . This means that if you have 10 elements, you will repeat up to the eighth element. Since you are using both < and length-1 . If you want to stick with .length-1 . You must change the condition to i<=b.length-1 .