c++ - 使用 openMP 的并行 qsort

Question

我正在尝试使用 openMP 在 C++ 中并行化 qsort() 函数，但我遇到了一些问题。总之，对于大量要排序的元素(例如:V=1000)，qsort 根本不起作用，我从不退出此函数(无限循环)。然后，我注意到我的并行版本的 qsort 比串行版本慢得多。 任何人都可以帮助我吗？ 这里的代码:https://dpaste.de/EaH0 .

这里是经过的平均时间，其中 kruscalP 是并行版本: 谢谢

Answer 1

当您写入 A、exch0 和 exch1 时，您的代码中有多个竞争条件，它们都是共享的。这不仅会损害性能，而且可能会给出错误的结果。不幸的是，您必须使用关键部分来解决这个问题，这也可能会损害性能，但至少会给出正确的结果。

#pragma omp for    
for (i = 0; i < N-1; i += 2) {
    #pragma critical
    {
        if (A[i].weight > A[i+1].weight) {
            temp = A[i];
            A[i] = A[i+1];
            A[i+1] = temp;
            exch0 = 1;
        }
    }
}

同样适用于下一个for循环。如果你想有效地做到这一点，你必须改变你的算法。也许考虑归并排序。