CODEWITHSUNDEEP
javasortingquicksort
NEX
NEX

Reputation: 77

Java QuickSort Stack Overflow with 20,000 or more integers

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

Upvotes: 1

Views: 582

Answers (2)

John Bollinger
John Bollinger

Reputation: 180181

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.

Upvotes: 0

Lajos Arpad
Lajos Arpad

Reputation: 76444

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.

Upvotes: 1

Related Questions