Ошибка stackoverflow в quicksort

Question

Итак, я сам пытался реализовать quicksort, но он генерирует stackoverflowerror, но я не могу найти причину.

Может кто-нибудь мне помочь?

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

Answer 1

Есть несколько ошибок, но непосредственный один вы удара, что в partition(), i не ограничивается быть между p и q. Вы довольно быстро оказываетесь в ситуации, когда p=2, q=3, но окончательное значение i равно 1. Это приводит к бесконечной рекурсии, поскольку qsort() продолжает называть себя идентичными аргументами.

Answer 2

ошибка переполнения стека означает, что условие остановки для рекурсии никогда не достигается, в этом случае p < q никогда не является истинным. Используйте отладчик, установите точку останова для этой строки и ищите, когда qsort() неоднократно рекурсивно вызывается с теми же параметрами.