Infinite loop/recursion when implement quicksort in java

Question

I'm attempting to implement quicksort in java in order to count the number of comparisons made, but I'm running into an infinite loop/recursive call situation, and I can't quite figure out where it's coming from.

Through debugging I've determined that the inner for loop runs however many times, and everything is only entered into "less" sublist, and then a recursive call is made to quicksort(less)

    private ArrayList<Comparable> quickSort(ArrayList<Comparable> qList) {
            ArrayList<Comparable> less = new ArrayList<Comparable>();
            ArrayList<Comparable> greater = new ArrayList<Comparable>();
            if (qList.size() <= 1)
                return qList;
            Comparable pivot = qList.get(qList.size() / 2);
            for (int i = 0; i < qList.size(); i++) {
                if ((qList.get(i).compareTo(pivot)) <= 0) {
                    comps++;
                    less.add(qList.get(i));
                } else {
                    comps++;
                    greater.add(qList.get(i));
                }
            }

            ArrayList<Comparable> toReturn = new ArrayList<Comparable>(
                    quickSort(less));
            toReturn.add(pivot);
            toReturn.addAll(quickSort(greater));
            return toReturn;

        }

If I just run the code with a list of size 20, I get this error

Exception in thread "main" java.lang.StackOverflowError
    at java.util.Arrays.copyOf(Unknown Source)
    at java.util.ArrayList.ensureCapacity(Unknown Source)
    at java.util.ArrayList.add(Unknown Source)
    at file.quickSort(CMSC351P1.thisClass:40)
    at file.quickSort(CMSC351P1.thisClass:48)

Antti Huima · Accepted Answer · 2011-04-15 01:13:34Z

2

The problem is that you add the pivot element itself to the 'less' list so the base case never terminates.

Example: You sort the list [0, 0] with your algorithm. The pivot element is ... 0. The 'less' list that your algorithm produces is again [0, 0], and you enter in infinite loop.

edited Apr 15, 2011 at 1:13

answered Apr 15, 2011 at 1:08

Antti Huima

25.6k3 gold badges55 silver badges71 bronze badges

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

3 Comments

user684934 Over a year ago

The actual problem in my opinion is that the pivot is NOT removed from the list when splitting to higher and lower lists; you're adding an element with every iteration...

Antti Huima Over a year ago

Yes, well, only after recursion though.

Rowhawn Over a year ago

ah that's right. I should have used remove rather than get. Thanks!

Ernest Friedman-Hill · Accepted Answer · 2011-04-15 01:09:46Z

1

You don't exclude the pivot from the less/greater sublists -- in fact, you explicitly include it in the sublist set. I suspect this means you'll get stuck with lists of two being infinitely sorted in many cases. You'll need to exclude the pivot from the less sublist.

answered Apr 15, 2011 at 1:09

Ernest Friedman-Hill

81.9k11 gold badges158 silver badges191 bronze badges

Comments

Larry Watanabe · Accepted Answer · 2011-04-15 01:19:50Z

0

You don't ensure that you partition the list so that the greater list is decreased in size by 1 or more or the less list is decreased in size by 1 or more.

At some point, if the pivot is the largest element in the list, then everything will go to the "less" list.

When you call it, the same thing will happen again.

answered Apr 15, 2011 at 1:19

Larry Watanabe

10.2k9 gold badges45 silver badges48 bronze badges

Collectives™ on Stack Overflow

Infinite loop/recursion when implement quicksort in java

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related