当我的 vector/array 尺寸变得太大时 VS 抛出异常

VS throwing exception when my vector/array size becomes too large

我的问题是,当我的数组大小变得太大时,我抛出了一个异常:“抛出 away.exe 中 0x005B3BC7 处未处理的异常:0xC00000FD:堆栈溢出(参数:0x00000001、0x01002F68)”。我需要能够 运行 此代码 array/vector 大小 n = 100000,但截至目前它仅适用于 n = 1000。超过此阈值的任何内容都会导致 VS 抛出堆栈溢出异常。建议我使用向量而不是数组,但这并没有解决问题。我添加了一个中断并开始调试。这就是我注意到在输入 quickSort 函数时会发生这种情况的地方。我假设,array/vector 大小如此之大,堆栈在被分区并划分为子数组时会变满。推荐的修复方法是什么?

#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);
}

您在 int M = (right - left) / 2; 中计算的中位数指数是错误的。

未优化的方程为

M = left + (right - left) / 2

相当于

2 * M = 2 * left + (right - left)

相当于

2 * M = left + right(假设 left + right 没有溢出)

相当于

M = (left + right) / 2

通过在较小的分区上递归,然后循环返回较大的分区,可以将堆栈开销减少到 O(log(n))。最坏情况下的时间复杂度仍然是 O(n^2).

void quickSort(std::vector<int> &arr, int left, int right) {
    while(right - left > 10){
        int M = left + ((right - left) / 2);
        int j = partition(arr, left, right - 1, M);
        if((j - left) < (right - j)){      // recurse on smaller, loop on larger
            quickSort(arr, left, j);
            left = j;}
        } else {
            quickSort(arr, j + 1, right);
            right = j;
        }
    }
    if(right - left > 0)
        insertionSort(arr, left, right);   // insertion sort needs a fix
}