CODEWITHSUNDEEP
javarecursionstack-overflowquicksort
Skeltar
Skeltar

Reputation: 25

I'm getting a java.lang.StackOverflowError in my quicksort

This is basicly a simple quicksort whiche uses arraylists but I can't find the reason why I get stuck in an endless recursion. In the end the only reslut I get is a stack overflow error.

 List<Integer> quicksort(List<Integer> toSort){

        if(toSort.size() > 1){
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            for(int i=0;i<toSort.size();i++){
                if(toSort.get(i) < toSort.get(toSort.size()/2))
                    left.add(toSort.get(i));
                else
                    right.add(toSort.get(i));
            }

            toSort = quicksort(left);
            toSort.addAll(quicksort(right));
            return toSort;

        }else
            return toSort;
    }

Upvotes: 0

Views: 76

Answers (1)

BeUndead
BeUndead

Reputation: 3618

Consider you have 2 elements in your toSort List (when it's first called), [2, 1].

First, you create two Lists, left and right.

You then populate these based on the 'pivot'. You use toSort.get(toSort.size() / 2); as the pivot. toSort.size() = 2, so toSort.get(1) = 1 (from the List above) in this case.

You then add the elements to different Lists based on whether they are LESS THAN this value. So that means you end up with (after the for loop has completed):

left = [], right = [2, 1].

You then call quickSort on both of these Lists again. Second time round, when calling toSort.addAll(quicksort(right)); you're back in the exact state as your first call, and so the above just happens again. Eventually this results in a stack overflow.

Your problem here is that you have mis-implemented the quicksort algorithm. I'd recommend reviewing the pseudo-code for the quicksort algorithm that you based your implementation from, and working through smaller steps of it at a time (and then asking for help when you identify the smallest step that you're misunderstanding).

Upvotes: 1

Related Questions