1
$\begingroup$

I have been exploring Dikstra partitioning Algorithm. Below are my given:

R = Red
W = White 
B = Blue

I have this unpartitioned array.

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

I want it partition in the format: R, W, B consecutively.

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

Given:

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

Below is my algorithm:

 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

The output should be like this:

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

My question is:

  1. Can I reduce the number of swaps? If yes, how?
  2. Is the algorithm applicable if there are 4 colors to be partitioned?

Thank you. I really need to understand this concept.

$\endgroup$
1
$\begingroup$

Short answer: No. Note that the worst case of this algorithm is when all elements are blue. In such case, you will need $2\cdot n$ swaps in the worst case. When all elements are blue the number of swaps can be zero.

Optimal algorithm:

I think that the following algorithm is the optimal one:

  1. Count the number of Reds, Blues and Whites in the array.
  2. Denote $n_{color}$ the number of elements of $color\in \{ Blue,Red,White \}$ in the array.
  3. Define $i=0, j=n_{Red}-1$, and $k=n_{Blue}+n_{Red}-1$, i.e., counters over the Reds,Blues and Whites arrays in the corresponding , respectively.
  4. Increase i,j,k until either the counter is lager than the size of the corresponding array (i.e., $i=n_{Red},j=n_{Blue}+n_{Red}$ and $k=n$), or that the corresponding element is not in the appropriate color (i.e., $a[i]$ is not red, $a[j]$ is not blue, $a[k]$ is not white). The algorithm stops iff when all counters are lager than the size of the corresponding array $i=n_{Red},j=n_{Blue}+n_{Red}$ and $k=n$.

Now, if $a[i]$ is blue and $a[j]$ is red, then we can swap between them, and increase the counters of $i$ and $j$ until possible. The same can be said if $a[i]$ is white and $a[k]$ is red or $a[j]$ is white and $a[k]$ is blue. Thus if there are two elements of $(a[i],a[j],a[k])$ with the same color- we can swap the corresponding pair, and increase the corresponding counters.

In the edge case where $a[i]$ is blue and $a[j]$ is white, and $a[k]$ is red, we must do $2$ swaps. The same happens if $a[i]$ is white and $a[j]$ is red, and $a[k]$ is blue.

The number of swaps in such algorithm is at most $\frac{2}{3}n$, in case the array begins with $\frac{n}{3}$ blues, continues with $\frac{n}{3}$ whites, and ends with $\frac{n}{3}$ reds.

I think that this is the optimal algorithm, I will try to show later the correctness.

2.Is the algorithm applicable if there are 4 colors to be partitioned? I think it does. In the worst case, you can use counting sort, which runs at $O(nk)$ given $n$ elements and $k$ colores.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.