并行快速排序分区中的段故障

Question

我正在尝试编写并行化的quicksort分区，但是不知何故，我遇到了段错误。

这是我的做法：

unsigned int NumList:: partition_par(vector<int>& keys, unsigned int low,
                                     unsigned int high)
{
    // Use the last element as the pivot
    int pivot = keys[high];

    unsigned int n = high - low + 1;
    if(n == 1) {
        return low;
    }
    int tmp[n-1];
    unsigned int lt[n-1]; // lt array used to add elements less than the pivot
    unsigned int gt[n-1]; // gt array used to add elements greater than the pivot

    #pragma omp parallel for
    for(unsigned int i = 0; i <= n-1; i++) {
        tmp[i] = keys[low + i];
        if(tmp[i] < pivot) {
                lt[i] = 1;
        }
        else {
                lt[i] = 0;
        }
        if(tmp[i] > pivot) {
                gt[i] = 1;
        }
        else {
                gt[i] = 0;
        }
    }

    for(unsigned int i = 1; i <= n-1; i++) {
        lt[i] = lt[i] + lt[i-1];
        gt[i] = gt[i] + gt[i-1];
    }
    unsigned int k = low + lt[n-1]; // get position of the pivot
    keys[k] = pivot;

    #pragma omp parallel for
    for(unsigned int i = 0; i <= n-1; i++) {
        if(tmp[i] < pivot) {
                keys[low + lt[i] - 1] = tmp[i];
        }
        else if(tmp[i] > pivot) {
                keys[k + gt[i]] = tmp[i];
        }
    }

    return k;
}

我不确定为什么会收到此段错误。我尝试调试它，但似乎仍然找不到问题。这里需要解决什么？

Answer 1

您的tmp，lt和gt数组不够长。您在循环中访问的最后一个元素是n-1，因此数组的大小必须为n，而不是n - 1。