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 + " ");
}
}
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.