并行快速排序分区中的隔离错误

Question

我正在尝试编写一个并行化的快速排序分区，但不知何故，我遇到了段错误。

这是我的做法：

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。

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

但是，这似乎不能正确排序元素。它似乎将一些元素放在错误的索引中(即，将一些数字放在其所需索引后面的一个索引(。这里似乎有什么问题？