CODEWITHSUNDEEP
javaquicksortstack-overflow
Patrik Bäckström
Patrik Bäckström

Reputation: 117

Quicksort Algorithm causing stack overflow

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;

    }

Upvotes: 1

Views: 974

Answers (3)

user166390
user166390

Reputation:

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 bale1:

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)
..

1 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.

Upvotes: 2

Marcin
Marcin

Reputation: 2409

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;

}

Upvotes: 3

Emil Vikstr&#246;m
Emil Vikstr&#246;m

Reputation: 91922

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.

Upvotes: 3

Related Questions