Stackoverflow error in my quicksort algorithm

Question

I've been working on this code for a few days with no luck because of a stack overflow error during recursion.

The problem states that our pivot is always the 0th element and through recursion we can sort an array by either swapping or creating new arrays and copy them into the original array. I chose to create 2 arrays since it is easier for me to understand but once I reach the recursive step i get this error.

I traced the algorithm and realized that the pivot element is always being placed in the lower array and may be the problem.

enter code here
public static void main(String[] args) {
    int[] arr = new int[] { 12, 7, 5, 8, 4, 6, 11, 15 };
    quicksort(arr);
    for (int i = 0; i < arr.length; i++) {
        System.out.print(arr[i] + " ");
    }
    System.out.println();

}



    private static int[] quicksort(int[] arr, int middle) {
    // Base case
    if (arr.length == 1) {
        return arr;
    }
    int[] upper = new int[arr.length];
    int[] lower = new int[arr.length];
    int upperIndex = 0, lowerIndex = 0;

    // Put the elements into their respective pivots
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] <= middle) {
            lower[lowerIndex++] = arr[i];
        } else {
            upper[upperIndex++] = arr[i];
        }
    }

    // Recurse, and sort the pivots
    lower = quicksort(lower, lower[0]);
    upper = quicksort(upper, upper[0]);

    // Combine lower, middle, and upper back into one array
    System.arraycopy(lower, 0, arr, 0, lowerIndex);
    arr[lowerIndex + 1] = middle;
    System.arraycopy(upper, 0, arr, lowerIndex + 2, upperIndex);
    return arr;
}

The result should be a sorted array in ascending order.

Despite a confusing similarity of names, Stack Overflow is not a very good way to debug a stack overflow. Instead, stepping through in a debugger (or even just adding some strategic print statements) will help you see what progress is being made on each recursive step and why the recursion continues down indefinitely. — manveti
– manveti, Commented Apr 5, 2019 at 21:43

rcgldr · Accepted Answer · 2019-04-06 01:32:12Z

As mentioned in Quimby's answer, both lower and upper are set to size arr.length. The code needs use a third parameter indicating the actual length, such as

quicksort(lower, lower[0], lowerIndex);
quicksort(upper, upper[0], upperIndex);

Since middle will end up in lower, if the data is already sorted, than at each level of recursion, all of the data ends up in lower, with zero elements in upper, resulting in an infinite recursion that is only stopped by stack overflow.

Since you're using separate arrays for the quicksort, you might want to consider a 3 way partition:

    public static void quicksort(int[] arr, int pivot, int size) {
        // Base case
        if (size < 2) {
            return;
        }

        int[] upper  = new int[size];
        int[] middle = new int[size];
        int[] lower  = new int[size];
        int upperIndex = 0, middleIndex = 0, lowerIndex = 0;

        // Put the elements into their respective arrays
        for (int i = 0; i < size; i++) {
            if (arr[i] < pivot) {
                lower[lowerIndex++] = arr[i];
            } else if (arr[i] == pivot){
                middle[middleIndex++] = arr[i];
            } else {
                upper[upperIndex++] = arr[i];
            }
        }

        // sort lower and upper
        quicksort(lower,  lower[0], lowerIndex);
        quicksort(upper,  upper[0], upperIndex);

        // Combine lower, middle, and upper back into one array
        System.arraycopy(lower,  0, arr, 0, lowerIndex);
        System.arraycopy(middle, 0, arr, lowerIndex, middleIndex);
        System.arraycopy(upper, 0, arr, lowerIndex+middleIndex, upperIndex);
    }

Quimby · Accepted Answer · 2019-04-05 21:44:41Z

0

Your upper and lower arrays don't seem to shrink at all, so the arr.length == 1 is never true. Easier implementation is to use indices and only the original array.

answered Apr 5, 2019 at 21:44

Quimby

19.4k4 gold badges40 silver badges61 bronze badges

Collectives™ on Stack Overflow

Stackoverflow error in my quicksort algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related