Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Bubble sort

Ls chin
Ranch Hand
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?

Bill Cruise
Ranch Hand
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
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
Posts: 12196
35
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++)

[ August 25, 2008: Message edited by: fred rosenberger ]

Ls chin
Ranch Hand
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++)

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
Rancher
Posts: 42968
73
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.

fred rosenberger
lowercase baba
Bartender
Posts: 12196
35
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
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.

Ls chin
Ranch Hand
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 ]

 Consider Paul's rocket mass heater.