Try to modify the partition that we saw in class to solve th

Try to modify the partition that we saw in class to solve the following problem in linear time: Given an array of n elements, each element having one of the values: red, white, or blue. Give an efficient algorithm for reordering the array so that all the reds come before whites, and all whites come before blue. The only operations permitted are to examine a key for its color, and a swap of two elements.

Solution

These problems is famous Dutch national flag problem.

The array is divided into four sections:

a[1..Lo-1] RED
a[Lo..Mid-] WHITE
a[Mid..Hi] unknown
a[Hi+1..N] BLUE

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=R and a[Lo..Mid-1]=W and a[Hi+1..N]=B; a[Mid..Hi] are unknown.
   2. case a[Mid] in
       0: swap a[Lo] and a[Mid]; Lo++; Mid++
       1: Mid++
       2: swap a[Mid] and a[Hi]; Hi--

   // Sort the input array, the array is assumed to
   // have values in {R, W, B}
   void sort012(char a[], int arr_size)
   {
   int lo = 0;
   int hi = arr_size - 1;
   int mid = 0;
     
   while (mid <= hi)
   {
   switch (a[mid])
   {
   case \'R\':
   swap(&a[lo++], &a[mid++]);
   break;
   case \'W\':
   mid++;
   break;
   case \'R\':
   swap(&a[mid], &a[hi--]);
   break;
   }
   }
   }

Time Complexity: O(n), we are traversing given elmenets only once