Segfault в параллельном разделе быстрой сортировки

Question

Я пытаюсь написать параллельный раздел быстрой сортировки, но каким-то образом получаю segfault.

Вот как я это делаю:

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

Я не конечно, почему я получаю этот segfault. Я попытался отладить его, но все еще не могу найти проблему. Что здесь нужно исправить?

Answer 1

Ваши массивы tmp, lt и gt недостаточно длинные. Последний элемент, к которому вы обращаетесь в своих циклах, - n-1, поэтому массивы должны иметь размер n, а не n - 1.

Использование std::vector (вместо нестандартного массива переменной длины ) может избежать других проблем (например, переполнения стека, если n слишком велик), и может обнаружить эту проблему при индексировании с использованием at.

Answer 2

Я изменил свой код, чтобы он выглядел так:

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 = new int[n];
    unsigned int* lt = new unsigned int[n];  // lt array used to add elements less than the pivot
    unsigned int* gt = new unsigned int[n];  // gt array used to add elements greater than the pivot
    unsigned int* prefix_lt = new unsigned int[n];
    unsigned int* prefix_gt = new unsigned int[n];

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

    prefix_lt[0] = lt[0];
    prefix_gt[0] = gt[0];

    // Uses prefix sum algorithm to get the proper positions of each element
    for(unsigned int i = 1; i < n; i++) {
        prefix_lt[i] = prefix_lt[i-1] + lt[i];
        prefix_gt[i] = prefix_gt[i-1] + gt[i];
    }

    unsigned int k = low + prefix_lt[n-1]; // get position of the pivot
    keys[k] = pivot;

    // Copies each element to the correct position
    #pragma omp parallel for
    for(unsigned int i = 0; i < n; i++) {
        if(tmp[i] < pivot) {
                keys[low + prefix_lt[i] - 1] = tmp[i];
        }
        else if(tmp[i] > pivot) {
                keys[k + prefix_gt[i]] = tmp[i];
        }
    }

    return k;
}

Однако, похоже, это не позволяет правильно отсортировать элементы. Кажется, что некоторые элементы помещаются в неправильные индексы (т. Е. Некоторые числа помещаются на один индекс позади желаемого индекса). В чем, кажется, проблема?