VS throws stack overflow exception when array/vector is too large

[F95]

My issue is that I get an exception thrown when my array size becomes too big: "Unhandled exception at 0x005B3BC7 in throw away.exe: 0xC00000FD: Stack overflow (parameters: 0x00000001, 0x01002F68)". I need to be be able to run this code with an array/vector size n = 100000, but as of right now it is only working with n = 1000. Anything past this threshold causes VS to throw a stack overflow exception. It was recommended that I use vectors instead of arrays, but this did not solve the issue. I added a break and began to debug. That is where I noticed that this occurs when the quickSort function is entered. I'm assuming that, with such a large array/vector size, the stack becomes full as it is partitioned and divided into subarrays. What would be a recommended fix for this?

#include <iostream>
#include <chrono>
#include <cmath>
#include <math.h>
#include <random>    
#include <vector>    
using namespace std;
    
// Insertion Sort    
void insertionSort(std::vector<int>& arr, int n) {
    for (int i = 1; i < n; i++) {
        int j, temp = arr[i]; // make a copy of a[i]
        for (j = i - 1; j >= 0; j--) { // starting "moving left"
            if (arr[j] > temp)
                arr[j + 1] = arr[j]; // inversion detected, move a[j] to the right
            else
                break; // index j is one spot to the left of where temp belong
        }
        arr[j + 1] = temp;
    }
    }

    // Partition
    int partition(std::vector<int>& arr, int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    swap(arr[pivotIndex], arr[right]); // move pivotValue to end

    // partition the array. upon finding an element smaller than pivot,
    // swap it ot the next position in the "store"
    int store = left;
    for (int i = left; i < right; i++) {
        if (arr[i] <= pivotValue) {
            swap(arr[store], arr[i]);
            store++;
        }
    }

    swap(arr[right], arr[store]); // swap pivot to its final position
    return store;
    }

    // Quick Sort
    // std::vector<int> &data, int left, int right
    void quickSort(std::vector<int> &arr, int left, int right) {
    // Perform IS when sub array(s) are less than 10
    if ((right - left) < 10) {
        insertionSort(arr, right);
    }
    else {
        int M = (right - left) / 2;
        int j = partition(arr, left, right - 1, M);
        quickSort(arr, left, j);    // sort the left of M
        quickSort(arr, j + 1, right); // sort the right of M
    }
    }

    // Check if array has been ordered
    bool isOrdered(std::vector<int>& arr, int n) {
    // array with 1 or no elements will always be sorted
    if (n <= 1)
        return true;

    for (int i = 1; i < n; i++) {
        if (arr[i - 1] > arr[i]) {
            return false;
        }
    }
    return true;
    }

    int main() {
    int input;

    // Prompt user with catch if input not within bounds
    do
    {
        cout << "----------------------------------------------------------------" << endl;
        cout << " Press 1 to exit the program " << endl;
        cout << " Press 2 to select the array that is sorted in increasing order " << endl;
        cout << " Press 3 to select the array that is randomly sorted " << endl;
        cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
        cout << "----------------------------------------------------------------" << endl;
        cin >> input;
    } while (input != 1 && input != 2 && input != 3 && input != 4);

    while (input != 1)
    {
        int n = 100000; // works with n = 1000

        vector<int> a(n); // originally int* a = new int[n]
        vector<int> b(n); // originally int* b = new int[n]
        vector<int> c(n); // originally int* c = new int[n]

        vector<int> a_c1(n);
        vector<int> b_c1(n);
        vector<int> c_c1(n);

        vector<int> a_c2(n);
        vector<int> b_c2(n);
        vector<int> c_c2(n);

        if (input == 2) {
            // Fill array with numbers in ascending order
            for (int i = 0; i < n; i++) {
                a[i] = i + 1;
            }
            
            // create first duplicate array
            for (int i = 0; i < n; i++) {
                a_c1[i] = a[i];
            }
            
            // get start time for IS
            auto start = std::chrono::steady_clock::now();
            insertionSort(a_c1, n);
            // get end time
            auto end = std::chrono::steady_clock::now();
            double elapsed_time_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end - start).count());
            double elapsed_time_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end - start).count());
            // output time to screen
            cout << "Elapsed time of Insertion Sort function: " << elapsed_time_ns << " ns or " << elapsed_time_ms << " ms" << endl;

            // create second duplicate array
            for (int i = 0; i < n; i++) {
                a_c2[i] = a[i];
            }

            // get start time for QS
            auto start2 = std::chrono::steady_clock::now();
            quickSort(a_c2, 0, n);
            // get end time
            auto end2 = std::chrono::steady_clock::now();
            double elapsed_time2_ns = double(std::chrono::duration_cast <std::chrono::nanoseconds> (end2 - start2).count());
            double elapsed_time2_ms = double(std::chrono::duration_cast <std::chrono::milliseconds> (end2 - start2).count());
            // output time to screen
            cout << "Elapsed time of Quick Sort function: " << elapsed_time2_ns << " ns or " << elapsed_time2_ms << " ms" << endl;

            cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(a_c1, n) << endl;
            cout << "After passing array through Quick Sort funtion, is it sorted?     " << isOrdered(a_c2, n) << endl;

        }

        else if (input == 3) {
            // seed the PRNG (MT19937) using a variable value (in our case, rd)
            std::random_device rd;
            std::mt19937 generator(rd()); // seed by variable input
            std::uniform_int_distribution<int> distribution(1, n); // random numbers need to be in range between 1, n

            for (int i = 0; i < n; i++) {
                b[i] = distribution(generator);
            }

            // create first duplicate array
            for (int i = 0; i < n; i++) {
                b_c1[i] = b[i];
            }

            insertionSort(b_c1, n);

            // create second duplicate array
            for (int i = 0; i < n; i++) {
                b_c2[i] = b[i];
            }

            quickSort(b_c2, 0, n);
           
            cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(b_c1, n) << endl;
            cout << "After passing array through Quick Sort funtion, is it sorted?     " << isOrdered(b_c2, n) << endl;
        }

        else {
            int temp_1 = n;
            for (int i = 0; i < n; i++) {
                c[i] = temp_1;
                temp_1--;
            }

            // create first duplicate array
            for (int i = 0; i < n; i++) {
                c_c1[i] = c[i];
            }

            insertionSort(c_c1, n);

            // create second duplicate array
            for (int i = 0; i < n; i++) {
                c_c2[i] = c[i];
            }

            quickSort(c_c2, 0, n);

            cout << "After passing array through Insertion Sort funtion, is it sorted? " << isOrdered(c_c1, n) << endl;
            cout << "After passing array through Quick Sort funtion, is it sorted?     " << isOrdered(c_c2, n) << endl;
        }

        // Prompt user again with catch if input not within bounds
        do
        {
            cout << "----------------------------------------------------------------" << endl;
            cout << " Press 1 to exit the program " << endl;
            cout << " Press 2 to select the array that is sorted in increasing order " << endl;
            cout << " Press 3 to select the array that is randomly sorted " << endl;
            cout << " Press 4 to select the array that is sorted in decreasing order " << endl;
            cout << "----------------------------------------------------------------" << endl;
            cin >> input;
        } while (input != 1 && input != 2 && input != 3 && input != 4);
        
    }
    
    exit(0);
}

[jonnin]

do not include both math and cmath, cmath is the correct version of it.

do you know how to compile with flags to max out the stack size? The default compile on some compilers may not do this.

line 46, change it to 100, or 1000, see if that helps? (this can be stupidly large if you use shellsort here, instead of an N*N one, like a millionish isnt bad!).

did you compile it in release / tweaked options or debug mode?

I think you are on the right track./

[helios]

Oh my god! Please use indentation consistently! Like this:

int foo(){
    int bar = 42;
    return bar;
}

Not like this:

    int foo(){
    int bar = 42;
    return bar;
    }

Your code looks like a single giant function.

Your partition function behaves extremely poorly if all the elements in the input have the same value. In that case, partition(arr, left, right, M) is always equal to right - 1, which causes the recursion to go out of control.

Also, your insertionSort() only accepts a length parameter. You need to pass it a start and end to sort correctly.

[jonnin]

its likely the second issue; the arrays are random so partition is ok for that I think?
did you check it with the 1000 size to ensure it actually sorted? Write a loop that complains..
for(i = 1; i < size; i ++)
if(array[i] < array[i-1]) cout << "sort failed"

[Ganado]

There are two common things that can cause stack overflow.
1. Is declaring a variable whose size is too big to fit on the stack. This is where you probably heard the vector suggestion, as the memory inside vectors is allocated with dynamic heap memory.
2. Recursing 1000s of times (perhaps infinite recursion).

However, in (1), if you were previously using arr = new int[n], this would not make a difference as far as stack overflows go. So this points towards the issue being (2).

For (2), any sane sorting algorithm would not need to do recursion more than around log(n) times, so if you have 100,000 elements, log₂(n) is about 16, which is not that much.

When I run your quickSort function, the first thing I notice is that you're doing a huge amount of unnecessary work when you call insertionSort inside quickSort, because you are passing 'right' as n. So if n = 99,000, and left = 89,991, you are still doing a very slow insertionSort on almost the full array.

Your stack overflow is because of point (2). You are indeed recursing thousands of times, well over what is needed for quickSort. The reason is probably helios' point.

If you add a parameter to your quickSort function for testing, e.g.

void quicksort(..., int level)
{
    cout << level << '\n';
    // ...
    quicksort(... , level + 1); 
}

You can see just how many times you start to recurse.

[F95]

For functions such as insertion sort and partition, they have to remain as is because I'm following a pseudo code. I have more flexibility with the quick sort function as there was some pseudo code provided but it was mostly fill-in-the-blank. I've tested this with smaller arrays/vectors and it works fine. I do understand how the code works in that the larger the array that is passed through, the more recursions I'm going to get and the more memory I'm going to use up. But these are the specifications.

[johnglen244]

When you partition and sort, you are going to need to get the available memory and if you are running low (going to run out before the next allocation), you are going to have to save memory to a file to free it up and retrieve it later.

[helios]

Disregard the above.

[ne555]

> If you add a parameter to your quickSort function for testing
> You can see just how many times you start to recurse.
you may also just run your program through a debugger and watch the call stack when it explodes or you interrupt it

> For functions such as insertion sort and partition, they have to remain as is
> because I'm following a pseudo code
in quicksort you have to sort a portion of your array, from `left' to `right'
but you are sorting from 0 to `right', ¿do you realise that that's a problem?

also, if you have function insertion_sort(array) and try to translate to c++
you may need to write void insertion_sort(std::vector<T> &array, int begin, int end); to allow passing a subarray to the function
otherwise, you'll need to copy the subarray, sort the copy and overwrite the portion in the original.



it seems that you have stack overflow because of a finite but with too many steps recursion
may try to increase the stack size ulimit -s