Почему я получаю переполнение стека, когда я включаю стержень в рекурсивных вызовах в алгоритме быстрой сортировки?

Question

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

Сбой программы только для определенного размера массива, ноЯ не могу понять, какое отношение они имеют к ошибкам.Например, программа дает сбой, когда я даю 40, но прекрасно работает для 50.

void quicksort(double* arr, int init, int fin) {
    if (init == fin) return;
    if (init == fin - 1) {
        if (arr[init] > arr[fin]) {
            double temp = arr[fin];
            arr[fin] = arr[init];
            arr[init] = temp;
        }
        return;
    }
    int smaller = init - 1;
    double pivot = arr[fin];
    for (int ind = init; ind < fin; ind++) {
        if (arr[ind] < pivot) {
            smaller++;
            double temp = arr[ind];
            arr[ind] = arr[smaller];
            arr[smaller] = temp;
        }
    }
    arr[fin] = arr[smaller + 1];
    arr[smaller + 1] = pivot;
    if(smaller>=init) quicksort(arr, init, smaller);
    if(smaller+2<=fin) quicksort(arr, smaller + 2, fin);
    return;
}

Это код, о котором идет речь.Это работает нормально, когда я говорю это так, но вызывает ошибки, когда я заменяю

if(smaller+2<=fin) quicksort(arr, smaller + 2, fin);

на

if(smaller+1<=fin) quicksort(arr, smaller + 1, fin);

Answer 1

if(smaller+1<=fin) эквивалентно if(true) (поскольку smaller+1 начинается как init и увеличивается не более чем fin-init раз), поэтому любой вызов с хотя бы тремя элементами обязательно будет повторяться на этой строке & mdash; и рекурсивный вызов может ничего не выполнить, если (например) все три элемента равны.

Answer 2

Еще один способ взглянуть на это.Предположим, что выбранный элемент поворота является наименьшим значением в разделе.Он переместится в начало диапазона.

[ 3 5 2 1 4]  // supposed we select 3 as the pivot
[ 2 1 3 5 4]  // after partitioning
[ 3 5 4] // the recursive call for the right "half"

Если мы снова выберем 3 в качестве точки разворота, в этом диапазоне ничего не изменится.И поэтому, когда мы снова возвращаемся в правую «половину», мы находимся в точно такой же ситуации.Мы не добились никакого прогресса, поэтому рекурсия будет продолжаться до тех пор, пока стек не переполнится.

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