多线程并行选择排序

Question

我有选择排序功能

inline void selection_sort(double* arrayPtr, int length_array)
{
    for (auto i = 0; i < length_array; i++)
    {
        for (auto j = i + 1; j < length_array; j++)
        {
            if (arrayPtr[i] > arrayPtr[j])
            {
                std::swap(arrayPtr[i], arrayPtr[j]);
            }
        }
    }
}

如何用多线程优化？

我只找到了快速排序的解决方案，但这些解决方案对我没有帮助。

Answer 1

免责声明：此仅针对作业要求。出于所有实际目的，std::sort 更好。

假设要求是必须执行一组精确的操作，但是独立的操作可以按任何顺序执行。

注意：

• 数组有length_array次遍历（索引为i）
• 每一道都必须按顺序完成。
• 但是，请注意（非正式地）第二遍的前半部分独立于第一遍的后半部分，只要完成第一遍的前半部分，两者都可以按任何顺序完成。

因此解决问题的一种可能方法是（要非常小心偏移错误，你必须计算出细节）

• 让线程 1 处理第一遍的前半部分。
• 等待两个线程完成当前步骤。
• 让线程 1 处理第一遍的后半部分，而线程 2 并发处理第二遍的前半部分。
• 等待两个线程完成当前步骤。
• 让线程 1 处理第二遍的后半部分，而线程 2 并发处理第三遍的前半部分。
• 等待两个线程完成当前步骤。
• 重复。
• 特例最后一关。
• 以某种方式处理偏移量。

Answer 2

How to optimize it with multithreading? I found solutions only for quick sort but but these solutions did not help me.

你找不到太多关于它的信息，因为这样做不是一个好主意。它不会有效率，选择排序的并行化与 insert sort 的并行化有一些相同的问题。即，此代码：

for (auto i = 0; i < length_array; i++)
{
    for (auto j = i + 1; j < length_array; j++)
    {
        if (arrayPtr[i] > arrayPtr[j])
        {
            std::swap(arrayPtr[i], arrayPtr[j]);
        }
    }
}

由于与内循环的相互依赖性，您无法有效地并行化外循环。因此，您已经限制了并行任务的数量及其粒度。然后你有交换阶段的数据依赖问题，你也需要解决这个问题，这也会影响并行版本的加速。

合并排序等算法更可并行化（即它们的并行化产生更好的加速）由于它们的分而治之性质，其中可以并行递归调用。

尽管如此，您可以在 中找到 OpenMP/C++ 中选择排序的并行版本。话虽如此，代码运行是并行的，但我怀疑没有太多（如果有的话）加速。