CODEWITHSUNDEEP
javaalgorithm
city
city

Reputation: 2154

Selection Rank Algorithm

Below is an implementation of the selection rank algorithm, which is used to find the elements before the Kth smallest elements in an array. Sometimes this program works well, but it sometimes fails due to stack overflow error (error below code snippet)

public static int rand(int left, int right){
    return left+(int)(Math.random()*(double)(right-left));
}

public static int rank(int[] array, int left, int right, int rank){
    int pivot = rand(left, right);  
    int leftend = partition(array, left, right, array[pivot]);

    int size = leftend - left +1;
    if(size == rank+1){
        for(int i=0; i<=leftend; i++)
        System.out.print(array[i]+" ,");
        return 0;
    }else if(size > rank)
        return rank(array, left, leftend, rank);
    else return rank(array, leftend+1, right, rank - size);

}   

public static int partition(int[] array, int left, int right, int pivot){
    while(true){
        while(left <= right && array[left] <= pivot)
            left++;

        while(right >= left && array[right] > pivot)
        right--;

        if(left > right)
        return left-1;

        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

 }

Error:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Random.nextDouble(Random.java:409)
    at java.lang.Math.random(Math.java:712)
    at mod.rand(mod.java:12)
    at mod.rank(mod.java:16)
    at mod.rank(mod.java:25)

I think maybe rand() is causing this problem, but I am not sure. Nor do I have any idea how to fix it.

Upvotes: 3

Views: 4717

Answers (3)

meriton
meriton

Reputation: 70584

The Javadoc of StackOverflowError says:

Thrown when a stack overflow occurs because an application recurses too deeply.

Since the default limit is quite high, a StackOverflowError usually indicates an infinite recursion.

To effectively diagnose such errors, use a decent IDE with debugging support, set an exception breakpoint for StackOverflowError, run your program, and inspect the local variables in the stack once the breakpoint is hit.

Doing that here, we get the following stack:

Random.nextDouble() line: 444 [local variables unavailable] 
Math.random() line: 716 
Test.rand(int, int) line: 5 
Test.rank(int[], int, int, int) line: 9 
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
Test.rank(int[], int, int, int) line: 18    
...

It would appear that rank invokes itself ad infinitum from line 18. Let's verify this by checking the local variables. For the topmost stack frame at line 18:

left    97  
right   107 
rank    5   
pivot   102 
leftend 107 
size    11

for the one below it:

left    97  
right   107 
rank    5   
pivot   101 
leftend 107 
size    11

for the one below that

left    97  
right   107 
rank    5   
pivot   105 
leftend 107 
size    11

Indeed, left and right are identical in these stack frames, i.e. the algorithm has stopped making progress. We also see that even though a different pivot index is chosen each time, leftend remains equal to right.

Looking at the array indexes in question, we see:

[97]    10  
[98]    10  
[99]    10  
[100]   10  
[101]   10  
[102]   10  
[103]   10  
[104]   10  
[105]   10  
[106]   10  
[107]   10

This looks like you are not handling the special case where all elements in the subrange are equal correctly.

Indeed, looking at the code we see that partition will always return right in such a case, and rank will call itself with identical parameters, recursing ad infinitum.

Take home messages:

  1. Inspecting the state of the program at the moment of failure (for instance with a debugger and break points) is very useful in finding bugs.
  2. Don't ignore corner cases.

Upvotes: 1

ZePoLiTaT
ZePoLiTaT

Reputation: 76

I assume you want your rand method to return a number between left(inclusive) and right(inclusive). However, the Math.random() method, returns a number between 0.0(inclusive) and 1.0(exclusive). Therefore, in the case when the size fo the subarray being evaluated is 2, (i.e: left=4 and right=5), the rand function will only be able to return 4 as a result. Try changing this line in your rand function to ensure it can include the upper bound:

return left+(int)(Math.random()*(double)(right-left));

for

return left+(int)(Math.random()*(double)(right-left + 1));

Upvotes: 2

Kostia
Kostia

Reputation: 271

The recursion never ends not because the input but because the usage of random, theoretically random can give you the same number each time. For example change to:

public static int rand(int left, int right)
{
    return right - 1;
}

Try it on input : 

int[] array= {1,2,11,67,35};
rank(array, 0, 4, 2);

and you will get java.lang.StackOverflowError on this input because the recursion never ends.

Upvotes: 1

Related Questions