Thursday, August 4, 2011

Dutch National Flag Problem

Given `N' objects coloured red, white or blue, sort them so that objects of the same colour are adjacent, with the colours in the order red, white and blue.
The technique to solve this problem is three way partitioning ie representing Red with 0 , White with 1 and Blue with 2 . The variables are lo , mid , hi .
lo = 1st position where value is not 0 .
hi = 1st position from end where value is not 2 .
mid = position past lo where value is not 1 .
sourcecode : //solution 2 dutch flag problem
void threewaypartitioning(int x[], int size){
int lo = 0, mid = 0, hi = size-1;
//move lo to a position where value is not 0
while ( lo < size && x[lo] ==0)
lo++;
//move hi to a position where value is not 2
while(hi >=0 && x[hi] == 2)
hi--;
//set mid to lo
mid = lo;
while (mid  <= hi)
{
//swap with lo if mid points to 0
//swap with hi if mid points to 1
//increment mid if it points to 1
if ( x[mid] == 0) {
std::swap(x[lo],x[mid]);
lo++;mid++;
}
else if (x[mid] == 1)
mid++;
else
{
std::swap(x[mid],x[hi]);
hi--;
}}}
Space Complexity = O(1) Time Complexity = O(n)

0 comments:

Post a Comment

Total Pageviews

Print