Java QuickSort Stack Overflow with 20,000 or more integers

Question

I am getting the following error when I run quicksort on an array with 20,000 or more integers.

Exception in thread "main" java.lang.StackOverflowError at project1.Project1.quickSort(Project1.java:31)

I am calling quickSort with p=0 and r=array.length-1

public static int[] createArray(int size)
{
    int []array = new int[size];
    for(int i=0;i<size;i++)
    {
        array[i]= randomGenerator.nextInt(100000);
    }
    return array;
}
public static void quickSort(int p, int r)
{
    if(p < r)
    {
        int q = partition(p, r);
        quickSort(p,q - 1);
        quickSort(q+1,r);
    }
}

public static int partition(int p,int r)
{
    int x = array[r];
    int i = p-1;
    for(int j=p;j<=r-1;j++)
    {
        if(array[j]<= x)
        {
            i++;
            swap(i,j);
        }
    }
    swap(i+1,r);
    return i+1;
}

public static void swap(int i, int j)
{
    int temp = array[i];
    array[i]= array[j];
    array[j]= temp;
}

public static void main(String[] args) 
{
    //Get all the required input data
    System.out.print("Size to be tested: ");
    sc = new Scanner(System.in);
    int input = sc.nextInt();
    float selectionAvg= 0,quickAvg= 0,countAvg=0, medianAvg=0;

    //Run the Quick sort algorithm
    array= startArray;
    int low= 0;
    int high = array.length-1;
    startTime= System.currentTimeMillis();
    quickSort(low, high);
    endTime = System.currentTimeMillis();
    time= endTime - startTime;
    System.out.println("Quick Sort Time: " + time + " milliseconds");  
    //printArray();
    quickAvg+= time;
}

You may want to look into so-called 'stackless recursion' via trampolining if you are getting a stack overflow. http://stackoverflow.com/questions/32685660/achieving-stackless-recursion-in-java-8 — CollinD, Oct 07 '15 at 18:11
@CollinD Agreed, although in this case I think there's something wrong with the code, 20k elements isn't a lot to sort, so a StackOverflowError suggests the poster isn't handling the indices correctly and is recursing forever. — blm, Oct 07 '15 at 18:13
Try separating your whole bunch of data into smaller sets, sort each smaller set with quicksort, and merge-sort them. — Zaphod Beeblebrox, Oct 07 '15 at 18:14
Your exception suggests that `partition()` is not functioning correctly, or that your starting array is pathological. You did not show how you initialize the array to sort. Is it possible that it retains its value from default initialization (all zeroes)? That would probably produce your symptoms. — John Bollinger, Oct 07 '15 at 18:16
I use the following to create the array myArray[i]= randomGenerator.nextInt(100000); — NEX, Oct 07 '15 at 18:42

score 1 · Accepted Answer · answered Oct 07 '15 at 18:22

1

You might consider modifying your program to be iterative. The basic idea of doing this is to use a stack on your own to handle the job which is currently handled by recursion.

Read this article for further reference.

answered Oct 07 '15 at 18:22

Lajos Arpad

64,414
37
100
175

John Bollinger · Answer 2 · 2015-10-07T18:40:49.347

One of the problems with the naive implementation of QuickSort is that recursion depth is O(n) in the worst case. That will occur if all or almost all of the partitionings assign only O(1) elements to one of the resulting partitions. The conditions that will trigger that depend on choice of pivot and on the data. In your particular case, it looks like that will happen if the array elements all have the same value or if they are sorted or reverse-sorted order. Such a condition likely explains your stack overflow.

Choice of pivot is really important for a QuickSort that performs efficiently for the widest variety of inputs. I'd suggest median-of-three or random selection as fairly good, relatively easy alternatives. Either of these would address the [reverse] sorted case, but additional changes would be needed to address the constant-value case.

Additionally, you can be certain to limit recursion depth to at most O(log n) by sorting only the smaller part of each partition recursively, and instead looping to sort the larger part. That's difficult to implement with partitioning performed in a separate function from the recursive calls, but it would address the constant-value case reasonably well.

Could you give me the code for the median of 3 algorithm you are talking about? — NEX, Oct 07 '15 at 18:40
Median of three means you look at three values -- typically the first, middle, and last, and choose as the pivot the one that falls in the middle in sorted order (that is, the median of those three values). So if the values at those positions (relative to the partition being subdivided) are `2`, `42`, and `7`, you choose `7` as the pivot. — John Bollinger, Oct 07 '15 at 18:44

Java QuickSort Stack Overflow with 20,000 or more integers

2 Answers2