srand (time (0)) и rand () вызывают ошибку переполнения стека

Question

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

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

void randomizedQuickSort(int arr3[], int start, int end) {
    int temp, pivot;
    int s = start, e = end;
    srand(time(0)); //<------------------------ ERROR THROWN

    // Partitioning
    while (s <= e) {
        pivot = 0 + (rand() % 5);
        while (arr3[s] < pivot)
            s++;
        while (arr3[e] > pivot)
            e--;
        if (s <= e) {
            temp = arr3[s];
            arr3[s] = arr3[e];
            arr3[e] = temp;
            s++;
            e--;
        }

        // Recursion
        if (start < e)
            randomizedQuickSort(arr3, start, e);
        if (s < end)
            randomizedQuickSort(arr3, s, end);
    }
}

Я ожидаю, что число будет между 0 и 4, но каждый раз оно генерирует -858,993,460. Вот скриншот ошибки и значений переменных:

^{(Нажмите на изображение, чтобы увеличить)}

Answer 1

Еще одна вещь:

Это:

pivot = 0 + (rand() % 5);
while (arr3[s] < pivot)
    s++;

для:

int arr3[] = { 1212, 1341, 61255, 1325, 125 };

заставляет s выйти за пределы, то есть: s станет большечем фактическая длина массива.

Это может привести к непреднамеренному поведению.

Answer 2

Наиболее вероятная проблема - слишком глубокие рекурсивные вызовы, которые переполняют стек. Также вам не нужно это srand() при каждом вызове рекурсии. srand() просто инициализирует генератор случайных чисел, и обычно это делается один раз, но не на каждом шаге цикла. Поместите это вне randomizedQuickSort(). Просто вызовите srand(time(0)); в начале программы (или текущий поток, если вы делаете это в отдельном потоке).

У вас есть отрицательное значение для pivot в окне Visual Studio «Watch / Autos», поскольку оно еще не инициализировано в момент переполнения стека, которое прерывает выполнение программы.

Также (как Стефан ответил) вы можете переполнить границы вашего массива здесь

while (arr3[s] < pivot)
    s++;
while (arr3[e] > pivot)
    e--; 

Проверьте, чтобы s и e находились в границах start и end:

while (arr3[s] < pivot && s < end - 1)
    s++;
while (arr3[e] > pivot && e > start)
    e--; 

Или присвойте pivot значение элемента случайного массива между start и end вместо просто случайного значения в некотором диапазоне.

Если у вас все еще будет переполнение стека, сделайте алгоритм итеративным или поместите меньше элементов в сортируемый массив данных.