jQuery in Action, 2nd edition*
The moose likes Beginning Java and the fly likes Bubble sort Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Bubble sort " Watch "Bubble sort " New topic
Author

Bubble sort

Ls chin
Ranch Hand

Joined: Jun 28, 2008
Posts: 99
Hi,

I'm learning to how do Bubble sort and I don't understand a couple of things. Why is it in the first loop, the (arr.length) has to minus 1, i.e. (j<arr.length-1)?

The inner loop also has a minus 1 there i.e. (i< arr.length-1-j). Why is that so?



Thank you for your help.
Bill Cruise
Ranch Hand

Joined: Jun 01, 2007
Posts: 148
The reason you subtract one from the array length is so you don't go off the end of the array. Array indices in Java go from zero to length-1 by design, so an array with a size of ten elements will index those elements by the integers 0-9.
Ls chin
Ranch Hand

Joined: Jun 28, 2008
Posts: 99
Hi Bill,
Thanks.
Originally posted by Bill Cruise:
The reason you subtract one from the array length is so you don't go off the end of the array. Array indices in Java go from zero to length-1 by design, so an array with a size of ten elements will index those elements by the integers 0-9.


I'm actually confused because when we iterate/loop through an array (e.g. to print), we don't have to do (arr.length-1). But to iterate/loop through this bubble sort array, we have to minus 1 from the array length??

Actually even if we don't minus 1 from the outer loop, the program will still run without error. But if we don't minus 1 from the inner loop, it will generate an arrayOutOfBounds error because it went off the end of the array as you've explained.

I just don't understand why the other for loop needs to be minus 1, maybe it is "optional"??

Thanks again.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11254
    
  16

think about what would happen if your array has one element in it. how many times do you have to loop through it to sort all the elements?

now what if your array had TWO elements - how many items might you have to move?

now think about printing an array. if your array has one element, how many items do you need to print? two elements?

in the outer loop, if you take out the -1, look at what happens at the end. assume your array has 10 elements. so, j becomes 10.

your inner loop will then run from 0 to (10 - 1 - 10) or -1, or not at all on the last time through. heck, you could even make it

for (int j=0; j<arr.length + 1000; j++)

and your code will run.
[ August 25, 2008: Message edited by: fred rosenberger ]

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Ls chin
Ranch Hand

Joined: Jun 28, 2008
Posts: 99
Hi Fred,
Thanks. I'm still trying to figure out this complicated array thingy.

Originally posted by fred rosenberger:
think about what would happen if your array has one element in it. how many times do you have to loop through it to sort all the elements?

With one element in the array - we only have to loop through it once. i.e. (arr.length).

Originally posted by fred rosenberger:
now what if your array had TWO elements - how many items might you have to move?[/QB]

If we have 2 elements in the array, we only have to move them or swap their position, only once. Right? Which is why the inner loop is (arr.length - 1).

Originally posted by fred rosenberger:
now think about printing an array. if your array has one element, how many items do you need to print? two elements?
[/QB]

For printing array, we have to loop through the entire array i.e. (arr.length).

Originally posted by fred rosenberger:
in the outer loop, if you take out the -1, look at what happens at the end. assume your array has 10 elements. so, j becomes 10.

your inner loop will then run from 0 to (10 - 1 - 10) or -1, or not at all on the last time through. heck, you could even make it

for (int j=0; j<arr.length + 1000; j++)

and your code will run.[/QB]

I put (int j=0; j<arr.length + 1000; j++) in my code and it runs without any error! I was surprised. Usually when the array length is wrong, it throws an ArrayOutOfBounds error. In this case, the array length didn't matter at all. I don't get it...

But my conclusion is that, whether we put (arr.length) or (arr.length-1) or (arr.length+1000) it doesn't matter - it just takes longer for the JVM to loop through the array to find the elements... Am I right?

Thank you.
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 41599
    
  55
I put (int j=0; j<arr.length + 1000; j++) in my code and it runs without any error! I was surprised. Usually when the array length is wrong, it throws an ArrayOutOfBounds error. In this case, the array length didn't matter at all. I don't get it...

But my conclusion is that, whether we put (arr.length) or (arr.length-1) or (arr.length+1000) it doesn't matter - it just takes longer for the JVM to loop through the array to find the elements... Am I right?


The reason it doesn't matter -for the j loop- is that j isn't used as an index into the array. Try doing that with the i index, and you'll get the exception.

It doesn't make sense for j to run further than arr.length-1, though. On the other hand, if j runs fewer than arr.length-1 times, the array may not be fully sorted.


Ping & DNS - my free Android networking tools app
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11254
    
  16

With one element in the array - we only have to loop through it once. i.e. (arr.length).

I would say this is not correct. if there is only one element in the array, the array is by definition already sorted. so, you need 0 loops.

basically, each loop through moves an element to the right spot. with a two element array, you loop once and you KNOW that one element is in the right spot, so you only have to deal with what's left. and what is left is a one element array, so you don't have to sort it.

With a 3 element array, the first loop puts one element in the right spot. the second loop puts the second element in the right spot, and the only remaining element has to be in the right spot, so you're done.

etc.

so, for an array of size N, you only need to put (N-1) elements in the right spot, and the last one has to be in the right spot by definition.
Ls chin
Ranch Hand

Joined: Jun 28, 2008
Posts: 99
Hi Ulf,
Thank you.

Originally posted by Ulf Dittmer:
The reason it doesn't matter -for the j loop- is that j isn't used as an index into the array. Try doing that with the i index, and you'll get the exception.


Ahh, I see - j is not used as an index for the array. With the inner i index, it throws an error if I increase or decrease the array range, it has to be specifically (-1) and (-j).

Originally posted by Ulf Dittmer:
It doesn't make sense for j to run further than arr.length-1, though. On the other hand, if j runs fewer than arr.length-1 times, the array may not be fully sorted.

Okay. Thanks for your explanations.
Ls chin
Ranch Hand

Joined: Jun 28, 2008
Posts: 99
Hi Fred,
Thanks.
Originally posted by fred rosenberger:
I would say this is not correct. if there is only one element in the array, the array is by definition already sorted. so, you need 0 loops.

This makes sense! If there is only one element, we don't need any sorting at all.

Originally posted by fred rosenberger:
basically, each loop through moves an element to the right spot. with a two element array, you loop once and you KNOW that one element is in the right spot, so you only have to deal with what's left. and what is left is a one element array, so you don't have to sort it.

During a swap, there is always one stationary element. And only the other 'non-stationary' element has to be moved.


Originally posted by fred rosenberger:
With a 3 element array, the first loop puts one element in the right spot. the second loop puts the second element in the right spot, and the only remaining element has to be in the right spot, so you're done.

etc.

so, for an array of size N, you only need to put (N-1) elements in the right spot, and the last one has to be in the right spot by definition.


Thanks a lot for your explanations. I understand it better now.
[ August 25, 2008: Message edited by: LS chin ]
 
jQuery in Action, 2nd edition
 
subject: Bubble sort