0

私は Dikstra パーティショニング アルゴリズムを調査してきました。以下は私の与えられたものです：

R = Red
W = White 
B = Blue

このパーティション化されていない配列があります。

| W | B  | R |  W  | R  | W | B |  W  |  W |

R、W、Bの連続した形式でパーティションを分割したい。

| R  |  ?  | W  |  B |
 0    i     j    k    n

与えられた:

 i = 0
 j = n
 k = n
 n = number of elements

以下は私のアルゴリズムです：

 while  (i < j)
 {
     case a[i]:
         R : i++;
         W : j--; swap(a[i], a[j]);
         B : j--; k--; swap(a[i], a[k]); swap(a[i], a[j]);
     end case 
 }
 //Done Sorting

出力は次のようになります。

|  R  | R  | W  |  W  |  W  |   W  |  W  |  B  |  B |

私の質問は次のとおりです。

  1. スワップの回数を減らすことはできますか? はいの場合、どのように？
  2. 分割する色が 4 つある場合、アルゴリズムは適用できますか?

ありがとうございました。私は本当にこの概念を理解する必要があります。

4

1 に答える 1