wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> arrange 0,1 and 2
        
(Message started by: rahul_832 on Jan 4^th, 2009, 9:42am)

Title: arrange 0,1 and 2
Post by rahul_832 on Jan 4^th, 2009, 9:42am

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.

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

Title: Re: arrange 0,1 and 2
Post by towr on Jan 4^th, 2009, 10:51am

Here's an older thread on this problem: http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1100111371

Title: Re: arrange 0,1 and 2
Post by rahul_832 on Jan 4^th, 2009, 10:52am

sorry i trying searching ...

but was unable to find

thanks

Title: Re: arrange 0,1 and 2
Post by towr on Jan 4^th, 2009, 11:30am

It's difficult to find older threads when the details of the problem keep changing, so I certainly won't hold it against you.

It seems to be known as the http://en.wikipedia.org/wiki/Dutch_national_flag_problem and is due to Edgar Dijkstra.

Title: Re: arrange 0,1 and 2
Post by rahul_832 on Jan 4^th, 2009, 11:38am

thanks towr

Title: Re: arrange 0,1 and 2
Post by howard roark on Jan 5^th, 2009, 10:30pm

@towr
I was just going through the old thread for this problem. I found the solution you posted:

Quote:

l=m=0
r=n-1
while (r > m)
{
while (a[r]=B)
r--;
switch (a[m])
{
case R : m++; break;
case W : swap(l,m), m++, l++; break;
case B : swap(m,r), r-- break;
}
}

Can you tell me if this code is stable sort? I think it is not stable.

Is there a stable solution for this problem which satisfies all the requirements?

Title: Re: arrange 0,1 and 2
Post by towr on Jan 6^th, 2009, 12:24am

on 01/05/09 at 22:30:29, howard roark wrote:

Can you tell me if this code is stable sort? I think it is not stable.

You're right, it isn't.

Quote:

Is there a stable solution for this problem which satisfies all the requirements?

I'm not entirely certain at the moment. I know it came up in one of the thread about this problem, but I haven't been able to find it.

Title: Re: arrange 0,1 and 2
Post by SMQ on Jan 6^th, 2009, 5:46am

Since we were unable to come up with a stable O(n) sort of just two values (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1213096186), I doubt we (the regulars on this forum) are aware of a stable single-pass sort of three values.

--SMQ

Title: Re: arrange 0,1 and 2
Post by towr on Jan 6^th, 2009, 6:02am

Meh, you never know, perhaps we were smarter 5 or so years ago. :P