StackOverFlow error for QuickSort Algorithm

Question

I am getting a StackOverflowError for this code. It says lines 184/185, which is where I initialize the split position (see below) and call the first recursive quickSort method. I can see that the code is having trouble exiting from the recursion, but I'm not sure where that is happening. Each time I call quickSort, it is on a smaller partition.

import java.util.*;

public class java2{

public static int MAXINT = 10000;
public static int[] intArray = new int[MAXINT];
public static int index;
public static long comparisons;

public static void main(String[] args)
{       
    System.out.println("SORTING ALGORITHM: Quicksort");
    // Create a random array of integers and sort using the CombSort algorithm
    // Print the number of items and comparisions

    for(index = 10; index <= 10000; index = index * 10)
    {
        if (index == 10)
            for(int i = 0; i < index; i++)
                System.out.print(intArray[i] + " ");
        comparisons = 0;
        generate(intArray, index);
        quickSort(intArray, 0, index - 1);
        output(comparisons);
    }
}

// Generate an array of random values between 0 and 10000
public static void generate(int[] valueArray, int count)
{
    Random generator = new Random();

    for(int temp = 0; temp < count; temp++)
    {
        valueArray[temp] = generator.nextInt(MAXINT) + 1;
    }
}

// Print the number of values in the array and the number of comparisons
public static void output(long count)
{

    System.out.println("Number of values in array: " + index);
    System.out.println("Number of comparisons required: " + count);
    System.out.println();
}

//Swap the given values and then assign them to the correct place in the array 
public static void swap(int[] value, int i, int j)
{
    int temp = value[i];
    value[i] = value[j];
    value[j] = temp;        
}

//Implement Quicksort algorithm
public static void quickSort(int[] value, int startIndex, int endIndex)
{
    int r = endIndex;
    int l = startIndex;
    int s;

    if (l < r)
    {
        s = partition(intArray, l, r);
        quickSort(intArray, l, s - 1); // StackOverflowError here
        quickSort(intArray, s + 1, r);
    }
}

//Partition an array into two parts
public static int partition(int[] value, int startIndex, int endIndex)
{       
    int r = endIndex;
    int l = startIndex;
    int p = value[l];
    int i = l;
    int j = r + 1;

    while(i < j)
    {
        while(value[i] < p)
        {
            i++;
            comparisons++;
        }

        while(value[j] > p)
        {
            j--;
            comparisons++;
        }

        swap(value, i, j);
    }

    swap(value, i, j);
    swap(value, l, j);

    return j;
}
} // end main

You could compare your version with working one: algs4.cs.princeton.edu/23quicksort/Quick.java — Sergey Chepurnov
– Sergey Chepurnov, Commented Nov 11, 2015 at 4:31
Try to find a very short example where it crashes and compare partial sorted results with what you would expect when you perform the quicksort by hand. — MrSmith42
– MrSmith42, Commented Nov 11, 2015 at 11:44
if your algorithm works for short arrays, you might simply need to increase your stack size. (For real world applications you might consider a non recursive version of QuickSort to avoid the stack probelmatic — MrSmith42
– MrSmith42, Commented Nov 11, 2015 at 11:48

Adam · Accepted Answer · 2015-11-11 05:30:53Z

4

Here are a few things to get you started with debugging.

You haven't posted your swap, but it's almost certainly incorrect. The way you're using it, its prototype would be void swap(int, int, int, int) which means it cannot have any effect on the value array. Try something like this:

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

and use it like this:

swap(value, i, j);

Next, get the length=10 case correct. Print out the full array before and after sort, verify that the output is correct. When I run your code on an all zero array I get an infinite loop.

Next, if you're still having problems, add print statements!

answered Nov 11, 2015 at 5:30

Adam

17.4k8 gold badges55 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Morgan4568771 Over a year ago

I have updated my swap method to how you described, and I added a print statement for the array of 10 elements, and it works for 10. Immediately following that, though, is the StackOverflowError again. It does not work for the next iteration, which is 100 elements. I will keep looking, but I'm not sure what changes between 10 and 100 elements, besides the actual number of elements of course, which shouldn't have an effect on anything.

Adam Over a year ago

The code you have posted does not reproduce the problem.

Morgan4568771 Over a year ago

I have updated the code in the original question to reflect what is giving me the error.

Adam Over a year ago

No you haven't. You just added the swap function. Copy/paste that into a .java file and see what you get.

Morgan4568771 · Accepted Answer · 2015-11-11 20:35:47Z

By restructuring the partition method, the problem has been fixed:

    public static int partition(int[] value, int p, int r)
    {
            int x = value[p];
            int i = p - 1;
            int j = r + 1 ;

            while (true)
            {
                    do
                    {
                        j--;
                        comparisons++;
                    }
                    while (value[j] > x);

                    do
                    {
                        i++;
                        comparisons++;
                    }
                    while (value[i] < x);

                    if (i < j)
                    {
                        swap(value, i, j);
                    }
                    else
                            return j;
            }
    }

Collectives™ on Stack Overflow

StackOverFlow error for QuickSort Algorithm

2 Answers 2

4 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Related