并行双向选择排序

本文关键字：排序 双向选择 并行 | 更新日期: 2023-09-27 18:15:35

我编写了并行实现双向选择排序的代码。我用的是c#，并且是并行的。调用函数。并行调用了2个循环，一个用于查找最小值，另一个用于查找最大值。然而，它没有排序。我想知道的问题是，因为这种类型的排序不能处理并行，因为每个循环依赖于存在于另一个循环的数据?还是我的代码出了问题?

Parallel.Invoke(
            () => 
                {                        
                    for (int i=0; i < array.Length / 2; i++)
                    {
                        int m;
                        int min = i;
                        for (m = i + 1; m < array.Length - 1; m++)
                            if (array[m] < array[min])
                                min = m;
                        //swap
                        int temp = array[min];
                        array[min] = array[m];
                        array[m] = temp;
                    }
                },
                () => 
                    {
                        for (int m = 0; m < array.Length / 2; m++)
                        {
                            int length = array.Length - 1;
                            int max = length - m;
                            int k;
                            for (k = length--; k > 0; k--)
                                if (array[k] > array[max])
                                    max = k;
                            //swap
                            int temp = array[max];
                            array[max] = array[k];
                            array[k] = temp;
                        }
                });

并行双向选择排序

我认为如果您在一个线程中搜索同一循环中的最小值和最大值会更容易:(java代码，但我认为您会理解该原则)

    int minimum, maximum;
    int k = size();
    for(int i = 0; i < size(); ++i)
    {
        --k;
        minimum = i;
        maximum = k;
        if(k - i <= 0)
            break;
        for(int j = i; j <= k; ++j)
        {
            if(greaterThan(minimum, j))
                minimum = j;
            if(lessThan(maximum, j))
                maximum = j;
        }
        if(minimum != i)
        {
            swap(minimum, i);
            if(maximum == i)
                maximum = minimum;
        }
        if(maximum != k)
            swap(maximum, k);
    }
你的代码的问题是:

假设这是一个数组:

[5,4,3,2,1]

迭代0:第一个线程将找到索引0上最小的元素
第一个线程查找索引4
处的最小元素迭代0:第二个线程将找到索引4
上最大的元素第二个线程查找索引0

处的最大元素

您将已经看到，这不会很好地结束，因为两个线程将执行索引0和4之间的交换，导致与现在相同的情况。

另一个问题是如果你的第一个线程是从m ->数组循环。长度- 1。如果同时线程2通过交换将最小元素(它不需要，因为它正在搜索最大值)从索引k移动到"max"。索引"max"为<"m"。这意味着第一个线程永远不会找到下一个最小值，因为它在它的位置之前被移动了。

编辑:经过考虑，我认为不可能实现一个直接的并行版本的选择排序。我最初推荐的版本确实不能工作，因为算法每次都找到相同的最小值，因为它没有改变输入数组。

可能的情况是，只对线程1在数组的前半部分执行选择排序(并且只允许它在这半部分中找到最小值)，而数组的后半部分用于第二个线程。最后，你可以用归并排序算法合并这两个部分。

这样你就可以使用2个以上的线程;例如，假设有"p"个线程。每个负责输入数组的N/p部分，其中"N"是输入大小。最后用归并排序算法归并每一部分。我从来没有自己实现过，所以我不能说它是否有效，但我认为会有更好的算法来并行化(比如归并排序本身)。

PS:关于上面发布的代码。我想除了下面这部分，其他的都很简单:

            if(maximum == i)
                maximum = minimum;

这是为了处理这样的情况:
……我……k
[1,4,3,1,5]

所以I = 1, k = 3(索引)

算法将找到:
max = index 1
Minimum = index 3

将最小值与索引i上的最小值交换后，情况如下所示:
……我……k
[1,1,3,4,5]

意味着最大值(整数4)实际上从索引"i"移动到索引"minimum"。如果我们执行swap(maximum, k)，它将会得到一个糟糕的结果。这就是为什么我们需要更新最大元素的索引，如果它位于索引i。

相关文章：