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.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
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?
Originally posted by fred rosenberger:
now what if your array had TWO elements - how many items might you have to move?[/QB]
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]
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?
With one element in the array - we only have to loop through it once. i.e. (arr.length).
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
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.
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.
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.
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.
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.
Don't get me started about those stupid light bulbs. |