wu :: forums - arrange 0,1 and 2

wu :: forums « wu :: forums - arrange 0,1 and 2 » Welcome, Guest. Please Login or Register. May 3^rd, 2024, 2:54pm
RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

   wu :: forums
   riddles
   cs (Moderators: towr, william wu, Eigenray, SMQ, Grimbal, ThudnBlunder, Icarus)
   arrange 0,1 and 2

« Previous topic | Next topic »

Pages: 1

Notify of replies

Send Topic

Author

Topic: arrange 0,1 and 2 (Read 1628 times)

rahul_832
Newbie

Gender:

Posts: 18

arrange 0,1 and 2
« on: Jan 4^th, 2009, 9:42am »

Quote

Modify

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.

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: arrange 0,1 and 2
« Reply #1 on: Jan 4^th, 2009, 10:51am »

Quote

Modify

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

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

rahul_832
Newbie

Gender:

Posts: 18

Re: arrange 0,1 and 2
« Reply #2 on: Jan 4^th, 2009, 10:52am »

Quote

Modify

sorry i trying searching ...

but was unable to find

thanks

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: arrange 0,1 and 2
« Reply #3 on: Jan 4^th, 2009, 11:30am »

Quote

Modify

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.

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

rahul_832
Newbie

Gender:

Posts: 18

Re: arrange 0,1 and 2
« Reply #4 on: Jan 4^th, 2009, 11:38am »

Quote

Modify

thanks towr

IP Logged

howard roark
Full Member

Posts: 241

Re: arrange 0,1 and 2
« Reply #5 on: Jan 5^th, 2009, 10:30pm »

Quote

Modify

@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?

« Last Edit: Jan 5^th, 2009, 10:54pm by howard roark »

IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: arrange 0,1 and 2
« Reply #6 on: Jan 6^th, 2009, 12:24am »

Quote

Modify

on Jan 5^th, 2009, 10:30pm, 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.

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

SMQ
wu::riddles Moderator
Uberpuzzler

Gender:

Posts: 2084

Re: arrange 0,1 and 2
« Reply #7 on: Jan 6^th, 2009, 5:46am »

Quote

Modify

Since we were unable to come up with a stable O(n) sort of just two values, I doubt we (the regulars on this forum) are aware of a stable single-pass sort of three values.

--SMQ

IP Logged

--SMQ

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender: male

Posts: 13730

Re: arrange 0,1 and 2
« Reply #8 on: Jan 6^th, 2009, 6:02am »

Quote

Modify

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

IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB

Pages: 1

Notify of replies

Send Topic


« Previous topic \| Next topic »