Quicksort Algorithm causing stack overflow

Question

SOLVED: posted in the end of THIS comment.

I keep getting this error and I can't find any explanation to why it occurs.

Exception in thread "main" java.lang.StackOverflowError
at java.util.Random.nextDouble(Random.java:444)
at java.lang.Math.random(Math.java:716)
at assignment6quickSort.M6.qsAlgorithm(M6.java:50)
at assignment6quickSort.M6.qsAlgorithm(M6.java:60)
at assignment6quickSort.M6.qsAlgorithm(M6.java:60)
at assignment6quickSort.M6.qsAlgorithm(M6.java:60)

I've been googling like crazy and it seems no one have had the same problem OR I'm to stupid to search for the right thing (utterly possible).

Anyway, I'm creating random numbers to find a pivot number for a generic quickSort and a couple of hours ago it worked some times but now I get this error every single time.

Please, I'm so frustrated... Hehe! What the h*ck am I doing wrong? How can this cause an overflow?

Here comes my code...

package assignment6quickSort;

import java.util.ArrayList;
import java.util.List;
import java.util.Comparator;


public class M6 {

    static M6Comparator<Integer> comp = new M6Comparator<Integer>();
    static Integer[] array = new Integer[20];
    static ArrayList qsSorted = new ArrayList();

    public static void main (String[] args) {       

        for (int i = 0; i < array.length; i++) {
            array[i] = (int)(50 * Math.random());
        }

        for (int i: array) {
            System.out.print(i + ", ");
        }

        quickSort(array, comp);
        System.out.println("\n");

        for (Object i: qsSorted) {
            System.out.print(i + ", ");
        }

    }

    static <T> void quickSort(T[] a, Comparator<? super T> comp) {

        ArrayList<T> temp = new ArrayList<T>();
        for (int i = 0; i < a.length; i++) {
            temp.add(a[i]);
        }

        qsSorted = qsAlgorithm(temp, comp);
    }

    static <T> ArrayList<T> qsAlgorithm(ArrayList<T> a, Comparator<? super T> comp) {

        ArrayList<T> L = new ArrayList<T>();
        ArrayList<T> G = new ArrayList<T>();

        if (a.size() <= 1) 
            return a;
        int pivot = (int)Math.random() * a.size();
        T pivotValue = a.get(pivot);
        for (int i = 0; i < a.size(); i++) {
            if (comp.compare(a.get(i), pivotValue) == -1 || comp.compare(a.get(i), pivotValue) == 0) {
                L.add(a.get(i));
            } else {
                G.add(a.get(i));
            }
        }

        L = qsAlgorithm(L, comp);
        G = qsAlgorithm(G, comp);
        L.addAll(G);

        return L;

    }

}

Additionally, here is my Comparator:

package assignment6quickSort;

import java.util.Comparator;

public class M6Comparator<E> implements Comparator<E> {

    public int compare(E original, E other) {

        return((Comparable<E>)original).compareTo(other);
    }

}

### SOLUTION ###

Apparently a classic recursive overflow error. Thanks a bunch to @pst and @Marcin for the help! Here is the revision of qsAlgorithm() method:

static <T> ArrayList<T> qsAlgorithm(ArrayList<T> a, Comparator<? super T> comp) {

        ArrayList<T> L = new ArrayList<T>();
        ArrayList<T> P = new ArrayList<T>();
        ArrayList<T> G = new ArrayList<T>();

        if (a.size() <= 1)
            return a;
        int pivot = (int)Math.random() * a.size();
        T pivotValue = a.get(pivot);
        for (int i = 0; i < a.size(); i++) {
            int v = comp.compare(a.get(i), pivotValue);
            if (v == -1) {
                L.add(a.get(i));
            } else if (v == 0) {
                P.add(a.get(i));
            } else {
                G.add(a.get(i));
            }
        }

        return concatenate(qsAlgorithm(L, comp), P, qsAlgorithm(G, comp));

    }

    static <T> ArrayList<T> concatenate(ArrayList<T> a, ArrayList<T> p, ArrayList<T> b) {

        a.addAll(p);
        a.addAll(b);

        return a;

    }

Are you sure that ((Comparable<E>)original).compareTo(other); is not calling itself? — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Mar 5, 2013 at 18:27
Nope... I'm not sure at all. Can't say that I fully understand the comparator and generics. So... Is it calling it self? — Patrik Bäckström
– Patrik Bäckström, Commented Mar 5, 2013 at 18:29
On a second look, no, it does not look like a call to itself. Never mind :) — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Mar 5, 2013 at 18:30

Marcin · Accepted Answer · 2013-03-05 19:31:34Z

4

You are entering recursive call too many times, until your stack overflows. The problem is that you reach a point in your main compare loop where you always add all elements to the temp array 'L', and none to 'G', so your recursive call:

L = qsAlgorithm(L, comp);

is always made with the same number of elements as the param:

ArrayList<T> a

so you never exit the recursion in line 49:

if (a.size() <= 1) 
    return a;

The solution would be to make an additional exit when your temp array has last 2 equal elements.

Edit: A quick and dirty fix... this is by no means efficient code. I used another 'E' collection for 'even' values and add them to the resulting list at the end.

static <T> ArrayList<T> qsAlgorithm(ArrayList<T> a, Comparator<? super T> comp) {

    ArrayList<T> L = new ArrayList<T>();
    ArrayList<T> E = new ArrayList<T>();
    ArrayList<T> G = new ArrayList<T>();

    if (a.size() <= 1) 
        return a;
    int pivot = (int)Math.random() * a.size();
    T pivotValue = a.get(pivot);
    for (int i = 0; i < a.size(); i++) {
        int v = comp.compare(a.get(i), pivotValue);
        if (v == -1) {
            L.add(a.get(i));
        } else if (v == 0) {
            E.add(a.get(i));
        } else {
            G.add(a.get(i));
        }
    }

    L = qsAlgorithm(L, comp);
    G = qsAlgorithm(G, comp);
    L.addAll(E);
    L.addAll(G);

    return L;

}

edited Mar 5, 2013 at 19:31

answered Mar 5, 2013 at 18:31

Marcin

2,4193 gold badges18 silver badges15 bronze badges

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

4 Comments

Patrik Bäckström Over a year ago

I'm not really sure of how that second exit would look. Do you mean that if an array has to identical values it should exit?

user166390 Over a year ago

@PatrikBäckström See en.wikipedia.org/wiki/Quicksort - note the pseudo-code concatenate(quicksort('less'), 'pivot', quicksort('greater')). For sorting sequences where many elements are expected to be the same, pivot could itself be a sequence, but it will be sufficient if it is just a single element (not included in either sub-problem). Quicksort is mostly academic anyway.

Patrik Bäckström Over a year ago

Yeah. I found a pseudo that look like this. codefor i := 0 to length[A]-1 (excluding pivot) do ... return quickSort(L) + pivotValue + quickSort(G)code and got really confused on how to concatenate the three values. That's why I ended up using L = ... and G = ... Futher more I don't really get how a.size() - 1 (length[A]-1 in pseudo) would take away my specific pivot value

Patrik Bäckström Over a year ago

Yeah. That solution got rid of the stack overflow. I somehow mixed it a little with what @pst said with the concatenate (made a separate method for it) but now it's only showing a few of the values

Emil Vikström · Accepted Answer · 2013-03-05 18:26:58Z

3

It is probably not the nextDouble function that really overflows your stack, it just so happens that you are calling it in each recursion step and therefore it is likely to be the function that reaches the limit. The real problem is that you are recursing too deep (a wrongful base case where you stop recursing, perhaps).

It looks like a.size is your variant. Make sure that a does indeed decrease with every step of your recursion.

answered Mar 5, 2013 at 18:26

Emil Vikström

92.3k17 gold badges144 silver badges178 bronze badges

1 Comment

Patrik Bäckström Over a year ago

Since I'm always dividing a into two parts before I call the same method I suppose it would decrease.

score 2 · Accepted Answer · 2013-03-05 19:52:29Z

2

Random is not causing the recursion that causes the stack overflow, but it is the straw that broke the camel's back.

The previous 2-ton hay bale¹:

at assignment6quickSort.M6.qsAlgorithm(M6.java:50)
at assignment6quickSort.M6.qsAlgorithm(M6.java:60)
at assignment6quickSort.M6.qsAlgorithm(M6.java:60)
at assignment6quickSort.M6.qsAlgorithm(M6.java:60)
..

¹ The problem in the posed code is that the pivot is included in the recursive sub-problem. Imagine the case of input [x,x] where both values are recursively selected in the L sequence as x <= x. R will always be terminal (0 elements), but L will never be terminal (2 elements).

See Quicksort on Wikipedia and note the pseudo-code concatenate(quicksort('less'), 'pivot', quicksort('greater')). That is, the pivot element is not included in the sub-problems.

edited Mar 5, 2013 at 19:52

answered Mar 5, 2013 at 18:27

user166390

4 Comments

Patrik Bäckström Over a year ago

But the array I'm sorting have only got 20 indexes. Even if I set the pivot to alway be a.size() / 2 it gives me the error. How can it possibly go so deep that it would cause an overflow?

Patrik Bäckström Over a year ago

Damn... That sounded way to theoretical to grasp. Honestly I can't understand what you're pointing at... /;

Patrik Bäckström Over a year ago

Aha... Yeah I saw that in the pseudo I used and I can't understand how to concatenate two array lists like that

Emil Vikström Over a year ago

Not including the pivot in the sublists is also a clever optimisation, since we trivially know where it should be in the result (between the two lists).

Collectives™ on Stack Overflow

Quicksort Algorithm causing stack overflow

3 Answers 3

4 Comments

1 Comment

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

1 Comment

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related