Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

You have an array containing only '0's, '1's and '2's. Club same items together in single scan.

let's try to understand problem:



algorithm:
i)  initialize i and j to 0 and  k to n-1 Where n is  number of balls
ii) while j <= k  do
            if pointer  j point to red ball than
                     swap a[i] and a[j];
and  perform i++; j++

           if pointer  j point to white ball than
just perform j++

           if pointer  j point to blue ball than
swap a[j] and a[k];
         and  perform  k--;

This problem is also known as Dutch National Flag Problem. Check out how Dutch flag looks like:

code:

#include <stdio.h>

//here red->0, white->1, blue->2
int arr[] = { 0,1,0,2,2,0,1,1,0 };      
int arr_size = sizeof(arr)/sizeof(arr[0]);

void swap(int *a, int *b);
void dutchflag( ); 

int main()
{
  int c; 
  dutchflag();  
  printf("\ndutch flag Order: ");
  for (c = 0; c < arr_size; c++)
    printf("%d ", arr[c]);
   
  return 0;
}
/* test function to to Sort the balls in dutch flag order*/
void dutchflag( )
{
 int i = 0,j=0 , k = arr_size - 1;
 
   while(j <= k)
   {
      switch(arr[j])
      {
         case 0:
            swap(&arr[i++], &arr[j++]);
           break;
         case 1:
          j++;
           break;
         case 2:
          swap(&arr[j], &arr[k--]);
           break;
      }
   }
}

/* Function to swap *a and *b */ 
void swap(int *a, int *b)
{
  int temp = *a;
  *a = *b;
  *b = temp;
}

output:-

dutch flag Order: 0 0 0 0 1 1 1 2 2

Time Complexity:  O(n)

SHARE