Рекурсия вызывает переполнение стека

Question

У меня возникла проблема с разделением при попытке реализовать алгоритм Quicksort. Моя реализация работает хорошо с массивами размером до 10 000, но над тем, что я получаю StackOverflowError. Обратите внимание, что это происходит только тогда, когда входные массивы находятся в порядке убывания. Случайно упорядоченные массивы могут быть до 10 000 000 000, прежде чем они вызывают одну и ту же проблему.

Я уверен, что в части есть что-то не так, когда я разбиваю массив, но я не могу понять, что случилось. Я пробовал отлаживать, но не имел успеха с поиском проблемы. Я понимаю, что ошибка вызвана слишком большим количеством рекурсивных вызовов, но, насколько я знаю, стек не должен переполняться, если разделение хорошо реализовано.

Заранее спасибо :)

Мой код:

public void sort(int[] v, int first, int last) { 


    if (first >= last) return; 
    //less than two elements left in subvector 

    // Partition the elements so that every number of 
    // v[first..mid] <= p and every number of v[mid+1..last] > p. 
    int[]subvector = new int[2]; 

    subvector = partition(v, first, last); 

    sort(v, first, subvector[0]-1); 
    sort(v, subvector[1], last); 

} 

И метод разделения:

private int[] partition(int[] v, int first, int last) { 
    int low = first; 
    int mid = first; 
    int high = last; 
    int pivot = getPivot(v, last); 


    while (mid <= high) { 
     // Invariant: 
     // - v[first..low-1] < pivot 
     // - v[low..mid-1] = pivot 
     // - v[mid..high] are unknown 
     // - v[high+1..last] > pivot 
     // 
     //  < pivot = pivot  unknown  > pivot 
     //  ----------------------------------------------- 
     // v: |   |   |a   |   | 
     //  ----------------------------------------------- 
     // ^  ^  ^  ^  ^
     // first  low  mid   high  last 
     // 
     int a = v[mid]; 
     if (a < pivot) { 
      v[mid] = v[low]; 
      v[low] = a; 
      low++; 
      mid++; 
     } else if (a == pivot) { 
      mid++; 
     } else { // a > pivot 
      v[mid] = v[high]; 
      v[high] = a; 
      high--; 
     } 
    } 

    return new int[]{low, high}; 
} 

Answer 1

Quicksort, как известно, O (N^2) в худшем случае, что когда вы даете ему отсортированный ввод и выбираете наихудший стержень (самый высокий или самый низкий элемент). Это также может привести к очень глубокой рекурсии, как вы видели. Вы не включаете механизм выбора поворота, поэтому я не могу быть уверен, что вы делаете, но вы, кажется, выбираете последний элемент. Некоторые поисковые запросы будут включать подробные дискуссии о выборе стержня для qsort.