Java implementation of Quicksort with Arraylist Troubleshooting

Question

I'm trying to implement the quicksort algorithm with ArrayList but can't seem to get this working. It gives me an error for my recursive return call in the sort() function. Please help!

This is the error I get: Exception in thread "main" java.lang.StackOverflowError

    public static void main(String[] args) {

    List<Integer> l = new ArrayList<Integer>();
    l.add(10); l.add(7); l.add(13); l.add(22); l.add(9);
    //l.get(2);


    System.out.println(sort(l));


}


public static List<Integer> sort(List<Integer> l) {

    if (l.size() <= 1) {
        return l;
    }

    int pivot = l.get(0);
    List<Integer> left = new ArrayList<Integer>();
    List<Integer> right = new ArrayList<Integer>();

    for (int i = 0; i < l.size(); i++) {
        if (l.get(i) < pivot) {
            left.add(l.get(i));
            //System.out.println(left);
        } else {
            right.add(l.get(i));
        }

    }
    return join(sort(left), sort(right), pivot);
}

public static List<Integer> join(List<Integer> left, List<Integer> right, int pivot) {

    List<Integer> l =  new ArrayList<Integer>();

    for (int i = 0; i < left.size(); i++) {
        l.add(left.get(i));
    }

    l.add(pivot);

    for (int i = l.size(); i < right.size(); i++) {
        l.add(right.get(i));
    }
    return l;
}

}

@CraigOtis Exception in thread "main" java.lang.StackOverflowError — rohstar
– rohstar, Commented Feb 9, 2014 at 21:11
Have you tried debugging your sort method? Often a Stack Overflow when implementing a divide and conquer search algorithm is an off-by-one error where you're calling the sort() method with the same arguments repeatedly, often when you get towards a "leaf" of the recursion. — Craig Otis
– Craig Otis, Commented Feb 9, 2014 at 21:14

Kuba Spatny · Accepted Answer · 2014-02-09 21:21:01Z

3

The problem is probably here:

you choose your pivot as:

l.get(0);

and then you add your pivot again:

int i = 0; i < l.size(); i++

as you start from zero!

So change it to start from 1:

int i = 1; i < l.size(); i++

EDIT: Another mistake is in your join() method - you must start from 0 for both arraylists:

for (int i = 0; i < right.size(); i++) {
        l.add(right.get(i));
}

edited Feb 9, 2014 at 21:21

answered Feb 9, 2014 at 21:14

Kuba Spatny

27k10 gold badges44 silver badges64 bronze badges

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

3 Comments

Craig Otis Over a year ago

Alternatively - use l.remove(0) when assigning the pivot, and leave the loop alone. (Unless you don't want to alter the provided List.)

rohstar Over a year ago

I changed the counter to 1, I get [7, 10] as a result

Kuba Spatny Over a year ago

@CraigOtis I don't think it's better solution, as remove() will probably have O(n) complexity for the first element..

NPE · Accepted Answer · 2014-02-09 21:16:23Z

0

Consider what happens if you choose the smallest element as your pivot. One of the two sub-lists will be empty, and the other would contain the entire original list, leading to infinite recursion.

answered Feb 9, 2014 at 21:16

NPE

503k114 gold badges970 silver badges1k bronze badges

Collectives™ on Stack Overflow

Java implementation of Quicksort with Arraylist Troubleshooting

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related