Quicksort Recursion - StackOverFlow

Question

I'm implementing a recursive quicksort however I'm receiving stackoverflow and not sure where the bug lies :(

I'm sorting 1 million ints from 10-50.

I works for sizes less than 1 million like 100 thousand etc.

public Quicksort(int NUM_TESTS, int NUM_ELEMENTS){
    num_tests = NUM_TESTS;
    num_elements = NUM_ELEMENTS;
}

private void start(){
    for (int i = 0; i < num_tests; i++){
        int[] d1 = dataGeneration(num_elements);
        qSortRecursive(d1,0,d1.length-1);
    }
}

public static void main(String args[]){
    Quicksort q = new Quicksort(1,1000000);
    q.start();    
}

private int[] dataGeneration(int n) {
    int[] d1 = new int[n];
    for (int i = 0; i < n; i++){
        d1[i] = (int)(Math.random() * ((50 - 10) + 1) + 10);
    }
    return d1;
}

private void qSortRecursive(int[] data, int left, int right){
    if(left < right){
        int pivot = partition(data,left,right);
        qSortRecursive(data,left,pivot-1);
        qSortRecursive(data,pivot+1,right);
    }
}

private int partition(int[] data, int left, int right){
    int pivot = left ;
    left++;
    while (left <= right){
        while (left <= right && data[left] <= data[pivot]) {
            left++;
        }

        while (left <= right && data[right] >= data[pivot]){
            right--;
        }

        if (left < right){
            swap(data,left,right);
            left++;
            right--;
        }          
    }

    if (data[right] <= data[pivot]){
        if (data[right] != data[pivot]){
            swap(data,right,pivot);
        }
        pivot = right;
    } 

    return pivot;
}

private void swap(int[] data, int i, int j){
    int temp = data[i];
    data[i] = data[j];
    data[j] = temp;
}

Do you understand the limitations of recursion? They're important to understand if you're using it. Unless you can guarantee that the function will be Tail Call optimized, it will always fail eventually with a StackOverflow. — Carcigenicate
– Carcigenicate, Commented Mar 25, 2017 at 12:04
Unoptimized recursion will continue to consume stack frames every time it recurses. Once you've taken up more space than the stack can hold, it "overflows". There's little you can do, especially in a language like Java. If you require it to process millions of elements, you'll need to switch to an iterative algorithm, or switch to another language that supports TCO. Java isn't a great language to use recursion in. — Carcigenicate
– Carcigenicate, Commented Mar 25, 2017 at 12:09
Yea well my assignment requires I do both recursive and iterative up to 1m elements so hmm — Ketameme
– Ketameme, Commented Mar 25, 2017 at 12:53
You can increase your stack size, but unless the teacher does the same when they test it, they'll get a StackOverflow when they run it. I'd hope that if your teacher is asking you to do this, they'd know the stack may be too small for this to work. Lookup how to increase stack size. I can't remember the command off the top of my head. — Carcigenicate
– Carcigenicate, Commented Mar 25, 2017 at 12:55

Ketameme · Accepted Answer · 2017-03-26 05:24:39Z

1

    private void qSortRecursive(int[] data, int left, int right){
    while (left < right){
        int pivot = partition(data,left,right);
        if (pivot - left < right - pivot){
            qSortRecursive(data, left, pivot - 1);
            left = pivot + 1;
        } else {
            qSortRecursive(data, pivot + 1, right);
            right = pivot - 1;
        }
    }

Performing a tail call by reducing number of recursion solved my problem, thanks for help everyone :)

answered Mar 26, 2017 at 5:24

Ketameme

1016 bronze badges

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

1 Comment

DimeCadmium Over a year ago

This is not even remotely a tail call. A tail call means that the 'current' stack frame can be replaced by the 'next' stack frame, because control will never need to return to the 'current' stack frame. Here, control must return to the 'current' stack frame in order to execute the left = or right =.

Martin Perry · Accepted Answer · 2017-10-03 09:04:43Z

1

You can try to rewrite the algorithm without recursion. Well, you remove recursion by adding your own stack and in that case you can have available the entire memory, not just size of stack.

Something like: http://alienryderflex.com/quicksort/

answered Oct 3, 2017 at 9:04

Martin Perry

9,5858 gold badges54 silver badges131 bronze badges

Collectives™ on Stack Overflow

Quicksort Recursion - StackOverFlow

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related