Dijkstra Partitioning Algorithm : Special Case

Question

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.

• greybeard: Have a look at gapped insertion sort for an idea.

Answer 1

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.