c# - 並列双方向選択ソート

Question

双方向選択ソートを並行して実装するコードを書きました。私は c# と parallel.invoke 関数を使用しました。2 つのループが並行して呼び出され、1 つは最小値を見つけ、もう 1 つは最大値を見つけました。それでも、それはソートされません。各ループは他のループに存在するデータに依存しているため、このタイプの並べ替えは並行して処理できないため、問題があるのではないかと思っていましたか?...または単に私のコードに何か問題がありますか?

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

Answer 1

1スレッドで同じループ内の最小値と最大値を検索すると簡単だと思います：（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: 2 番目のスレッドは、インデックス 4 に配置する最大要素を
見つけます。インデックス 0

両方のスレッドがインデックス 0 と 4 の間でスワップを実行し、結果として現在と同じ状況になるため、これが適切に終了しないことは既におわかりでしょう。

別の問題は、最初のスレッドが m -> array.length - 1 からループしている場合です。同時に、スレッド 2 が最小要素 (最大値を検索しているため必要ありません) をインデックス k から "max "スワップ経由。インデックス "max" は < "m" です。つまり、最初のスレッドはその位置より前に移動されたため、次の最小値を見つけることはありません。

編集:検討の結果、選択ソートの単純な並列バージョンを実装することは不可能だと思います。私が最初に推奨したバージョンは、入力配列を変更しなかったため、アルゴリズムが毎回同じ最小値を見つけるため、実際には機能しませんでした。

可能なことは、配列の前半でスレッド 1 のみを使用して選択ソートを実行し (その半分で最小値のみを検出できるようにする)、配列の後半を 2 番目のスレッド用にすることです。そして最後に、両方の半分をマージソートアルゴリズムでマージできます。

このようにして、常に 2 つ以上のスレッドを使用できます。たとえば、スレッド数を「p」とします。それぞれが入力配列の N/p 部分を担当し、「N」は入力サイズです。そして最後に、すべての部分をマージソートアルゴリズムでマージするだけです。私はそれを自分で実装したことがないので、効率的かどうかはわかりませんが、並列化するためのより良いアルゴリズムがあると思います (mergesort 自体のように)。

PS: 上記のコードについて。この部分を除いて、すべてがかなり簡単に見えると思います。

            if(maximum == i)
                maximum = minimum;

それは、次のような状況に対処するためです
。. . 私 。. . k
[1, 4, 3, 1, 5]

したがって、i = 1 および k = 3 (インデックス) です。

アルゴリズムは以下を見つけます:
最大 = インデックス 1
最小 = インデックス 3

最小値をインデックス i の最小値と交換すると、状況は次のように変化します
。. . 私 。. . k
[1, 1, 3, 4, 5]

最大値 (整数 4) が実際にインデックス "i" からインデックス "minimum" に移動したことを意味します。swap(maximum, k) を実行すると、悪い結果になります。そのため、インデックス i に配置されていた場合、最大要素のインデックスを更新する必要があります。