stackoverflow error in quicksort

Question

So I've been trying to implement a quicksort myself, but it generates a stackoverflowerror, but I can't seem to find what the cause is.

Can someone help me?

public static int partition(int[] a, int p, int q){
    int i = 0;
    for (int j = p; j < q; ++j){
        if(a[j] <= a[q]){
            int tmp = a[j];
            a[j] = a[i];
            a[i] = tmp;
            i++;
        }
    }
    int tmp = a[i];
    a[i] = a[q];
    a[q] = tmp;
    return i;
}

public static void qsort(int[] a, int p, int q){
    if(p < q){
        int x = partition(a, p, q);
        qsort(a, p, x - 1);
        qsort(a, x + 1, q);
    }
}

public static void main(String args[]){
    int[] a = {4, 6, 2, 9, 8, 23, 0, 7};

    qsort(a, 0, a.length - 1);

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

+1 for stackoverflow question in stackoverflow :)

FailedDev
– FailedDev

2011-10-19 13:30:25 +00:00
Commented Oct 19, 2011 at 13:30 — FailedDev
– FailedDev, Commented Oct 19, 2011 at 13:30

NPE · Accepted Answer · 2011-10-19 13:34:22Z

2

There are several bugs, but the immediate one you're hitting is that in partition(), i is not constrained to be between p and q. You pretty quickly end up in a situation where p=2, q=3 yet the final value of i is 1. This results in infinite recursion as qsort() keeps calling itself with identical arguments.

answered Oct 19, 2011 at 13:34

NPE

503k114 gold badges970 silver badges1k bronze badges

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

Comments

millimoose · Accepted Answer · 2011-10-19 13:31:05Z

2

A stack overflow error means the stop condition for the recursion is never reached, in this case p < q is never true. Use a debugger, set a breakpoint for that line, and look for when qsort() is repeatedly recursively called with the same parameters.

answered Oct 19, 2011 at 13:31

millimoose

40.1k11 gold badges88 silver badges138 bronze badges

Collectives™ on Stack Overflow

stackoverflow error in quicksort

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related