用于我的快速排序功能的高长度数组的堆栈溢出

Question

需要使用并测量随机数组排序所需的时间。我收到堆栈溢出错误，如下所示：

COM301 Lab 3.exe 中 0x00007FF64EEC2634 处未处理的异常：0xC00000FD：堆栈溢出（参数：0x0000000000000001、0x0000004DB18B3FC8）。

我认为我的代码可能存在一些问题，如下所示。快速排序并不完全完美，但这就是我让它适用于较小数组的方法。该错误在交换中弹出，但我认为这不是问题。这是代码：

#include <ctime>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

#ifndef QuickSort
using namespace std;

static void swap(int arr[], int& x, int& y) {
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

void minMax(int arr[], const int& size, int& min, int& max) { 
    for (int i = 0; i < size; i++) {
        if (arr[i] < min)
            min = arr[i];
        if (arr[i] > max)
            max = arr[i];
    }
}
//QuickSort:____________________________________________________________________________________________________________________________________________
//partitioning for quicksort
int partition(int arr[], int start, int end) {
    int pivot = arr[start]; //array is randomly generated, so pivot selection is trivial
    int i = start + 1;
    int j = end;

    while (i <= j) {    //While I is less than J, increment closer to the pivot until a suitable switch is found.
        while (i <= j && arr[i] < pivot)
            i++;
        while (i <= j && arr[j] > pivot)
            j--;
        if (i < j)
            swap(arr, i, j);    //suitable match found, switch i and j only if theyre not out of scope of their proper placement
        else
            break;
    }
    swap(arr, start, j);    //put pivot in its correct position

    return j;
}

void quickSort(int arr[], int start, int end) {
    if (start + 1 < end) { //as long as the array length is more than 1, continue recursing
        int p = partition(arr, start, end);

        //right side recursion
        quickSort(arr, p + 1, end);

        //left side recursion
        quickSort(arr, start, p);

        
    }
}

//MergeSort:_________________________________________________________________________________________________________

int main() {
//initialization of arrays, and array qualities
    const int size = 250;
    int max = 0;
    int min = 999999999;
    int arr[size];
    int arrC1[size], arrC2[size], arrC3[size], arrC4[size];

//Random generation seeded by the clock, as well as initialization of start/stop time variable
    srand(static_cast<unsigned>(time(0)));
    clock_t startTime, endTime;
    clock_t timeElapsed;

// Creation and printing of unsorted array  
    for (int i = 0; i < size; i++) {
        arr[i] = rand();
    }
    cout << "Randomly generated array(unsorted): \n";
    for(int i = 0; i < size; i++)
        cout << arr[i] << endl;


//copying of array to be used by sorting algorithms
    for (int i = 0; i < size; i++) {
        arrC1[i] = arr[i];
    }
    for (int i = 0; i < size; i++) {
        arrC2[i] = arr[i];
    }
    for (int i = 0; i < size; i++) {
        arrC3[i] = arr[i];
    }
    for (int i = 0; i < size; i++) {
        arrC4[i] = arr[i];
    }

//Run and print Quick sort
    startTime = clock();
    quickSort(arrC1, 0, size - 1);
    endTime = clock();
    timeElapsed = (endTime - startTime) * 1000;

    cout << "Start Time: " << startTime;
    cout << "\n End Time: " << endTime;
    cout << "\n \n \n Quick Sorted Array: \n";
    for (int i = 0; i < size; i++)
        cout << arrC1[i] << endl;
    cout << "Time Elapsed: " << timeElapsed;



}

我是一名学生，希望进入软件工程行业，所以请温柔对待我。我想学习如何以简单的方式解决这个问题，如果可能的话，这些方式很容易理解（我有一些编程经验，但在这个级别上不多）。此外，我对时钟（）函数有问题，所以如果有人可以向我展示最新的修复程序，那就太好了。我需要以毫秒/纳秒为单位，因为秒太大而无法测量。

注意：代码非常不成熟，我只是想修复自动取款机的快速排序。我需要最终实现合并排序、选择排序等。不需要任何帮助，我只是想我会提到它，哈哈。

我尝试过将交换设置为静态（认为这没有帮助，但 vss 推荐它）。我还尝试过在函数指针中使用整数来减少内存使用量，但这会扰乱稍后对它们进行的操作。我还搞乱了使左侧递归在 p - 1 处结束，因为我知道这就是快速排序的工作原理（但它破坏了我所拥有的）。我搞乱了 if (start + 1 < end) of the quickSort function but IDK how to properly optimize it. I've also tried setting the pivot differently but anything fancy I tried broke the program, even at the smaller array level. Really though I'm sure its something dumb that someone who knows quick sort could show me. If you can I'd really appreciate the help, thanks!

Answer 1

为了避免堆栈溢出，请在较小的分区上递归，在较大的分区上循环。

void quickSort(int arr[], int start, int end) {
    while (start < end) {
        int p = partition(arr, start, end);
        if(p - start <= end - p){       // recurse on smaller, loop on larger
            quickSort(arr, start, p);
            start = p + 1;
        } else {
            quickSort(arr, p + 1, end);
            end = p;
        }
    }
}

也使用新的|删除数组的[]。不要显示大数组：

int main() {
//initialization of arrays, and array qualities
    const int size = 16*1024*1024;
    int max = 0x80000000;
    int min = 0x7FFFFFFF;
    int i;
    int *arr   = new int [size];
    int *arrC1 = new int [size];
    int *arrC2 = new int [size];
    int *arrC3 = new int [size];
    int *arrC4 = new int [size];

//Random generation seeded by the clock, as well as initialization of start/stop time variable
    clock_t startTime, endTime;
    clock_t timeElapsed;

// Creation and printing of unsorted array
    for (int i = 0; i < size; i++)
        arr[i] = rnd32();

//copying of array to be used by sorting algorithms
    for (int i = 0; i < size; i++)
        arrC1[i] = arr[i];
    for (int i = 0; i < size; i++)
        arrC2[i] = arr[i];
    for (int i = 0; i < size; i++)
        arrC3[i] = arr[i];
    for (int i = 0; i < size; i++)
        arrC4[i] = arr[i];

//Run and print Quick sort
    startTime = clock();
    quickSort(arrC1, 0, size - 1);
    endTime = clock();
    for (i = 1; i < size; i++) {
        if (arrC1[i - 1] > arrC1[i])
            break;
    }
    if (i == size)
        cout << "passed" << endl;
    else
        cout << "failed" << endl;
    timeElapsed = (endTime - startTime) * 1000;
    cout << "Time Elapsed: " << timeElapsed << endl;
    delete[] arrC4;
    delete[] arrC3;
    delete[] arrC2;
    delete[] arrC1;
    delete[] arr;
    return 0;
}