Ошибка времени выполнения C ++ с алгоритмом быстрой сортировки, создающим ошибку дампа стека

Question

Код работает нормально, когда я пытаюсь size = 20000 , и кажется, что он терпит неудачу, когда я пытаюсь size = 50000 , выдавая следующую ошибку:

2 [] cppapplication_4 7628 cygwin_exception :: open_stackdumpfile: трассировка стека дампов в cppapplication_4.exe.stackdump

long long compares; // for counting compares
long long swaps; // for counting swaps
bool counted_less(int n1, int n2) {
    ++compares;
    return n1 < n2;
}

void counted_swap(int& n1, int& n2) {
    ++swaps;
    int t = n1;
    n1 = n2;
    n2 = t;
}

int* partition(int* start, int* stop) {
    int noUse=99;
    int* pivot = (stop - 1); // you can randomly pick one as the pivot
    int* i = start;
    int* j = stop - 1;
    for (;;) {
        while (*i < *pivot && i < stop)
        {
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
            ++i;
        }
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
        // skip "low" on left side
        while (*j >= *pivot && j > start) {
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);
            --j;
        }
            counted_less(noUse,noUse);
            counted_less(noUse,noUse);

        // skip "high" on right side
        if (i >= j) 
        {
            counted_less(noUse,noUse);
            break;
        }
        else
        {
            counted_less(noUse,noUse);
        }
        swap(*i, *j);
        counted_swap(noUse,noUse);// swap out-of-place items
    }
    swap(*(stop - 1), *i); 
    counted_swap(noUse,noUse);// swap pivot to the final place i
    return i;

}
void quickSort(int* start, int* stop) {
    int noUse=99;
    if (start>= stop){
        counted_less(noUse,noUse);
        return;
    }
    else
    {
        counted_less(noUse,noUse);
    }
    int* pivot = partition(start,stop);
    quickSort(start, pivot);
    quickSort((pivot +1), stop);
}

int main()
{
    int size = 20000;
    int* data = new int[size];
     for (int i = 0; i < size; ++i) data[i] = i;
     quickSort(data, data + size);
}

Я думаю, что ошибка означает, что я превышаю ограничение хранилища типов данных, я думаюпроблема была в том, что я использовал int, поэтому я изменил все int на long long, и это все равно не помогло.И по логике кода я не думаю, что мы меняем размер массива.Поэтому я не уверен, что вызвало ошибку.

Answer 1

Возможно, вы переполняете стек.Вот почему рекурсия плохая.

В качестве временного решения попробуйте увеличить размер стека, связав его с --stack 16777216:

$ g++ -Wl,--stack,16777216  . . .

== EDIT ==

Также ваш выбор точки разворота на (end - 1) не очень хорош.Попробуйте установить центр в середине.

    int* pivot = (stop - start)/sizeof(int*)/2 + start;