Selection Rank Algorithm

Question

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.

Answer 1

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));

Answer 2

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.