Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Sorting negative and positive integers in an array in Java -- out of bounds exception  RSS feed

 
Frank Poupard
Ranch Hand
Posts: 65
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello, given an array of int, I would like to put all the negative values (in the following example "-1") in the right part of the array. The expected output here is : 25,3,5,12,21,7,-1,-1,-1
In the first for loop, I count the occurrence of the negative values, and in the second one, I swap them.
I get an out of bound exception unfortunately, which I don't really understand...Is this handmade algorithm right anyway ? Thanks for insights.


 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why are you subtracting 1 from tab.length? And what's the purpose of counting negative numbers if you just need to move them to the end of the array?
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The exception is going to occur on the first line of your swap. Walk through the iterations and track the value of the variable i and the expression you're using for the index into tab.
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your input array contains a "4". Why is there no "4" in your expected results array? And why only three "-1" values in the expected outcome, when there are four "-1" values in the original?
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And your algorithm is seriously flawed. For example, what would happen if element 5 were "-1" instead of "12" ?
When i==3, you find tab[3] == -1, so you exchange it with tab[tab.length - leftLength + i] = tab[ll-7+1] = tab[5] = -1,
so all you do is exchange two "-1" values and go on to the next value, leaving a negative value at index 3.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're not using the right idiom for processing an entire array:


You'd use tab.length - 1 if you have something like this:

Here, since you have an expression i+1 inside the loop, the upper bound of the loop variable i needs to be adjusted so your index expression i+1 doesn't run out of bounds, resulting in an ArrayIndexOutOfBoundsException
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:
Here, since you have an expression i+1 inside the loop, the upper bound of the loop variable i needs to be adjusted so your index expression i+1 doesn't run out of bounds, resulting in an ArrayIndexOutOfBoundsException


But the loop termination is i < tab.length-1 so it is OK to add 1 to i without going out-of-bounds.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Fred Kleinschmidt wrote:But the loop termination is i < tab.length-1 so it is OK to add 1 to i without going out-of-bounds.

That's what I said, isn't it?

I wrote:You'd use tab.length - 1 if you have something like this: ...

The code I gave after that was meant to show a CORRECT usage. I suppose it would have been clearer if I had written: "Instead of using just tab.length per the normal idiom, you'd need to adjust the loop index upper bound by one, as shown in the code above, so your ..."
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@Frank: You should rethink your algorithm.

Here's how I solved this: Think of it like a modified Bubble Sort, except you're not really sorting the elements in any order, just making the negative values "bubble up" to the end of the array. The idea is to iterate through the array and swap a negative number with the next non-negative number. The most tricky part is finding the index of the next non-negative number and guarding against referencing an index that is out of bounds.


The alternative algorithm allows you to eliminate one level of nesting inside the loop.

So for tab = { 25, 3, 5, -1, 4, 12, -1, -1, 21, 7, -1 }, here's how it would go:

first iteration, i = 0
skip to next iteration because tab[0] is positive (25)

next iteration, i = 1
skip to next iteration because tab[1] is positive (3)

next iteration, i = 2

skip to next iteration because tab[2] is positive (5)

next iteration, i = 3
don't skip because tab[3] is negative (-1)
find the index j greater than i such that tab[j] is positive (4)
that means j == 4
swap tab[3] and tab[4]
now, tab[3] == 4 and tab[4] == -1

next iteration, i = 4
don't skip because tab[4] is negative (-1)
find the index j greater than i such that tab[j] is positive (12)
that means j == 5
swap tab[4] and tab[5]
now, tab[4] == 12 and tab[5] == -1

next iteration, i = 5
don't skip because tab[5] is negative (-1)
find the index j greater than i such that tab[j] is positive (21)
that means j == 8
swap tab[5] and tab[8]
now, tab[5] == 21 and tab[8] == -1

... and so on


 
Frank Poupard
Ranch Hand
Posts: 65
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for your help. My algo was indeed totally wrong as it offered no guarantee to swap a negative value with a positive value.
According to the pseudo code you gave me, I came up with the following code, which seems to work. It yields 25 3 5 4 12 21 7 -1 -1 -1 -1 as expected.



But I'm sure there is a quicker one, I'm open to any comment and suggestions !
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You should also try your algorithm with another sequence such as {-1, -1, 2, 3, 4 } If that works, you have another test. Always test with several combinations, especially ones that differ significantly (for example, here we try one that starts with a positive followed by a negative, and also one that starts with a negative followed by a positive, one that has multiple negatives together, one that has multiple positives, etc..
 
Fred Kleinschmidt
Bartender
Posts: 560
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Also, you can easily speed up this algorithm. In the inner loop, after you make a swap, arr[i] will always be non-negative, so there is no need to continue with the rest of the inner loop because the first part of the if-test is guaranteed to be false. Just put a break statement after swapping.
 
Junilu Lacar
Sheriff
Posts: 11146
160
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You can do this without breaks or with just one break in the outer loop:

Notes:

Line 1 - outer loop condition uses (i < arr.length - 1) instead of the idiomatic (i < arr.length) because the inner loop index, j, is initialized to (i + 1) - see my previous comment about this

Line 3 - inner loop condition includes arr[i] < 0. This causes the inner loop to terminate if arr[i] is positive to begin with or after a positive number is swapped into arr[i]. This eliminates the need to use another if-statement, a break statement, and a boolean swapped variable.

Line 4 - condition for the if-statement is simplified because the loop condition ensures that arr[i] < 0 inside the inner for-loop.

Line 11 - this statement is really optional but it saves a few iterations if there are many negative numbers in the array. This terminates the outer loop when no swap happens in the inner loop and arr[i] is still negative. That means the rest of the array after arr[i] does not have any positive numbers.
 
Frank Poupard
Ranch Hand
Posts: 65
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the break statement. With 100 000 random integers, with the break the sort is done in 1,981 s, without 9,117s (just one try).
 
Frank Poupard
Ranch Hand
Posts: 65
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Junilu, I've seen your post just afterwards, this is indeed a more elegant way to do it...
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!