0

SOLVED: I was instantiating a new Random object with every recursive call. I put it as a static variable out of Quicksort and now it works perfectly fine.

I'm programming Quicksort in Java for a school homework, but i got stuck. I'm choosing pivots randomly using nextInt() method from Random class. This means that i'm calling nextInt() in every recursive step. My quicksort does the work perfectly in arrays with 20000 elements. But when I try to sort an array with 40000 elements, this StackOverflowError appears 

   java.lang.StackOverflowError: null (in java.util.Random)

I've searched this error on google buy nothing helps me. My guess is that I ran out of random ints, but i'm so noob in java that i don't even buy my own guess.

Here's my code (spanish is my first language, sorry for the lame english and the spanish code)

public static void quicksort(String[] A, int min, int max){// llamar ord(A, 0, n-1);
    if(min >= max){
        return;
    }
    Random rand = new Random(); 
    int pivote = particionar(A, min, max, rand);
    quicksort(A, min, pivote-1);
    quicksort(A, pivote + 1, max);
    }

public static int particionar(String[] A, int min, int max, Random rand){    
    int menores = min + 1;
    int mayores = max;

    int pivote = rand.nextInt(max-min+1) + min;
    String pivotstr = A[pivote];
    //dejar pivote al principio
    String aux = A[min];
    A[min] = A[pivote];
    A[pivote] = aux;

    while(menores <= mayores){
        if(A[menores].compareTo(pivotstr) <= 0){
            menores++;
        }
        else{//intercambiar
            String aux2 = A[menores];
            A[menores] = A[mayores];
            A[mayores] = aux2;
            mayores--;
        }
    }
    //mover pivote donde corresponde
    String aux3 = A[min];
    A[min] = A[mayores];
    A[mayores] = aux3;

    return mayores;

}
JasonMArcher
  • 14,195
  • 22
  • 56
  • 52
ekauffmann
  • 150
  • 10
  • 1
    I would say that before actually posting anything on StackOverflow, you should probably read what "StackOverflow Error" really means... – sashkello Jun 14 '13 at 06:43

2 Answers2

0

StackOverflowError is what you get when your recursion runs too deep.

Solution: convert it to an iterative version. Way to go from recursion to iteration

Community
  • 1
  • 1
Lorenzo Marcon
  • 8,029
  • 5
  • 38
  • 63
0

Your program is generating too many levels of recursive calls and running out of memory on the stack. One solution is to increase the stack size at run time as described here. The other is to convert from recursion to iteration, as suggested by lorenzo.marcon.

Java's default random number generator is a linear congruential generator with a 48 bit seed size, so it should have a cycle length on the order of 2**48. That means you don't run out of random ints, but rather you repeat the sequence after that many values.

A huge contributor to your stack overflow problem is that you're instantiating a new Random object with every recursive call. You wouldn't dig a new well every time you want a drink of water, most people would dig a single well and revisit it for more water. Similarly, recommended practice is to instantiate one static Random object and revisit it for more values unless you really know what you're doing - You almost never want multiple Random objects.

pjs
  • 18,696
  • 4
  • 27
  • 56
  • Thank you, i'll see what i cand do about it. But the thing is that the StackOverflowError is happening in java.lang.Random, and I don't know how to manipulate the Random class to solve this. Also, when I call Quicksort without a a random pivot, but with the first element of the array, ir works perfectly. – ekauffmann Jun 14 '13 at 14:48
  • Calling quicksort with a different pivot leads to an entirely different sequence of recursive calls - you can't compare apples and oranges. – pjs Jun 14 '13 at 15:03
  • You are right. Thank you :) Now i solved my problem. I instanced the variable Random rand = new Random() out of quicksort and now it works perfectly fine with arrays over 100.000 elements ! – ekauffmann Jun 14 '13 at 15:18
  • I would bet that it also is running faster, even on cases that it already worked for. – pjs Jun 14 '13 at 16:24
  • nope, it's the same. Also, I used Heapsort (iterative) with the same array and my quicksort is 5 times slower... something's really wrong, or my computer is extremely slow with recursion – ekauffmann Jun 14 '13 at 16:31