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

        riddles >> cs >> Sort the array containing elements of three colors
        
(Message started by: cssomnath on Nov 10th, 2004, 10:29am)
Title: Sort the array containing elements of three colors
Post by cssomnath on Nov 10th, 2004, 10:29am
An array contains elements of the red, black, and white. The problem is to sort the array

There is an easy solution of O(n) by calculating the frequency of each element. But my interviewer told to it in exact n time not even in 2n or something.
Title: Re: Sort the array containing elements of three co
Post by towr on Nov 10th, 2004, 10:44am
I can see a reason not to use the frequency (f.i. if each elements has more characteristics than only color). But I don't see what is meant by 'exactly n time'  You can't be limited to n elementary operations, because it will take at least that much to get through the array without doing anything. O(n) = O(2n) so it doesn't make much sense.
Title: Re: Sort the array containing elements of three co
Post by cssomnath on Nov 10th, 2004, 10:50am
What I mean is in ONE PASS. Or execute the getColor() function on each element only once.
Title: Re: Sort the array containing elements of three co
Post by towr on Nov 10th, 2004, 12:05pm
How about something like


Code:
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;
 }
}


(probably still some details to work out, but it should give a general idea)

[edit]corrected while condition from (r > l) to (r > m) [/edit]
Title: Re: Sort the array containing elements of three co
Post by tseuG on Nov 10th, 2004, 2:08pm
     I'm not sure if this can be done with only a single getColor access per element, without using an additional linear storage. Here is another way with >n getColor accesses.

r = 0;

for(i = 0; i < n; i++)
{
     if(a[i] == 'R')
     {
           a[i] = a[r];
           a[r++] = 'R';
     }
}

w = r;

for(i = r; i < n; i++)
{
     if(a[i] == 'W')
     {
           a[i] = a[w];
           a[w++] = 'W';
     }
}
Title: Re: Sort the array containing elements of three co
Post by towr on Nov 10th, 2004, 2:45pm
It's easy enough to do with linear storage, at most I'd need to remember the color for three elements at a time.
Title: Re: Sort the array containing elements of three co
Post by cssomnath on Nov 11th, 2004, 8:18am
I didn't get it. You mean it can be done by just remembering the color of three elements. That is only using three extra storage.
Title: Re: Sort the array containing elements of three co
Post by tseuG on Nov 11th, 2004, 12:01pm
   Right, you would just need to remember whether r has been changed, before entering the inner while loop to invoke getColor again.
Title: Re: Sort the array containing elements of three co
Post by TenaliRaman on Nov 11th, 2004, 11:01pm
err this may sound stupid but can anyone give me an example of an input and expected output for this problem ??
Title: Re: Sort the array containing elements of three co
Post by towr on Nov 12th, 2004, 3:47am
example input: {R1, B2, W3, B4, R5, W6, B7, R8, R9, R10, B11}
possible example output: {W3, W6, R1, R5, R8, R9, R10, B2, B4, B7, B11}
Title: Re: Sort the array containing elements of three co
Post by vikashkodati on Nov 14th, 2004, 12:05pm
towr:

I think its "while(r > m)" and not "while(r > l)". The later condition might not arise in cases where sizeof(whites) != 0.

Thx

-Vikash.
Title: Re: Sort the array containing elements of three co
Post by towr on Nov 14th, 2004, 12:58pm
Yes, quite right.  :)
Title: Re: Sort the array containing elements of three co
Post by puzzlecracker on Nov 23rd, 2004, 5:38pm
Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi--
Title: Re: Sort the array containing elements of three co
Post by mamaheshwari on Dec 7th, 2004, 5:54am
I Hope this will work -

#include<stdio.h>


char a[]={'R','B','W','B','B','W','R'};

int main()
{
int r = 0;
int n = 7;
int b = n-1;
int i=0;
int j= n -1;
while ( i < n && j > 0  )
{
if(a[i] == 'R')
{
 a[i] = a[r];
 a[r++] = 'R';
}
if(a[j] == 'B')
{
  a[j]=a[b];
  a[b--]='B';
}
i++;
j--;
}

}
Title: Re: Sort the array containing elements of three co
Post by Joe on Dec 14th, 2004, 5:34am
another solution:

three_colors(Array A)   {
 int whiteBorder = -1,redBorder=0,blackBorder=n+1;
 while(redBorder<=blackBorder)  {
       switch(A[redBorder])   {
           case "Red":  redBorder++;
           case "White":  {
                  whiteBorder++;
                   swap(A[redBorder],A[whiteBorder]);
                   redBorder++;
              }
            case "Black":  {
                 blackBorder--;
                 swap(A[redBorder],A[blackBorder]);
                 redBorder++;
            }
   }
}
Title: Re: Sort the array containing elements of three co
Post by towr on Dec 8th, 2005, 12:15pm
Seems a bit long for such a small problem..
Title: Re: Sort the array containing elements of three co
Post by rene on Dec 9th, 2005, 2:06pm
another one with "one pass"

int  temp,pos1,pos2,pos3,color1_initialised=0,color2_initialised=0,color3_initialsed=0;

for(int i=0;i<n-1;i++)
{
   if(color(b[i]='r')
  {
       if(!color1_initialised)   // first red ball
       {  
            flag1=1;pos1=i;a[pos1++]=b[i];}
       else
       {temp=b[i];
         for(int j=i-1;j<pos-1;j++)
         {    a[j+1]=a[j];}
          a[pos1++]=temp;
        if(color2_initialsed) pos2++;
        if(color3_initialsed) pos3++;
      }
 }
// similarly for other colors
Title: Re: Sort the array containing elements of three co
Post by rene on Dec 11th, 2005, 8:28pm
hello guys...... i am waiting eagerly for ur criticisms...

reply.. if the above algo is the best...... ;D
Title: Re: Sort the array containing elements of three co
Post by towr on Dec 12th, 2005, 1:24am
You have a nested for-loop. Doesn't that make it slower than it has to be?
Title: Re: Sort the array containing elements of three co
Post by JohanC on Dec 12th, 2005, 3:26am

on 12/11/05 at 20:28:03, rene wrote:
hello guys...... i am waiting eagerly for ur criticisms...

If you really want critisims ...
- as Towr notices, the double for-loop probably makes things quadratic in speed (I write probably, because the second for-loop has a very obscure function)
- flag1,flag2 and flag3 aren't meaningful names for variables
- you have a variable temp that is neither declared nor used
- your second for-loop has a terminating condition on i that seems always fulfilled (at least if pos is meant to be pos1?); also it doesn't change j during the loop

Probably you still have quite some work to get your code readable and workable  :-/
Title: Re: Sort the array containing elements of three co
Post by rene on Dec 12th, 2005, 8:28pm
thank u towr and johanc;

   i have modified the code for better readability ;D
johanc.......

 and as for the second for loop.. it's only to shift one step...eg:

  r1,y1,y2,b1,r2,y3

  r1,r2,y1,y2,b1,y3 (r2 is placed properly)

 r1,r2,y1,y2,y3,b1( completed sort in one pass)

....... the average case will be lot better than quadratic and it's "ONE PASS" towr
Title: Re: Sort the array containing elements of three co
Post by towr on Dec 13th, 2005, 2:40am
You can call it one pass, but if you have two loops something more is happening.. Even though the second loop may only just shift one step, in the worst case it can shift over half the array.

If you want to use sorting, you can adapt quicksort for a better result. (Using a lexical ordering, where e.g. (red, a) > (blue,b) > (white,c) )
Since you only need partial sorting (just on color, leaving the order otherwise the same), you can even make extra improvements.
Title: Re: Sort the array containing elements of three co
Post by Quartz on Feb 8th, 2007, 5:02pm
This works perfectly with O(n)


char[] a={'R','B','W','B','B','W','R','B','W','B','B','W','R','B','B','W','R','R','B','B','W','R'};

int i=0;
int n = a.Length ;

 int posR =0; // Get the first position of Red to put it there

 int posB=n-1; // Get the last Position to put Blue  there

while ( i < a.Length  )
{

   if (a[i]=='R') //try to put all RED in front
      {
        a[i] = a[posR];
        a[posR] = 'R';
        posR++;
      }
 
   if (a[i]=='B') //try to put all BLUE at the end
     {
       if (i < posB)
         {
              a[i] = a[posB];
              a[posB] = 'B';
              posB--; // 2nd last position for blue
              i--; // dec i incase the switched item is red
          }
      }

i++;
}
Title: Re: Sort the array containing elements of three co
Post by Grimbal on Feb 9th, 2007, 3:08am
You could do  while ( i <= posB  ) ...
Title: Re: Sort the array containing elements of three co
Post by Quartz on Feb 9th, 2007, 9:22am
yes, you are right thanks for adding that
forthe example though ( i< posB) was working but it might not if in the lastposB we have W
Title: Re: Sort the array containing elements of three co
Post by msaha on Aug 6th, 2010, 1:09pm

on 02/08/07 at 17:02:27, Quartz wrote:
This works perfectly with O(n)


char[] a={'R','B','W','B','B','W','R','B','W','B','B','W','R','B','B','W','R','R','B','B','W','R'};

int i=0;
int n = a.Length ;

 int posR =0; // Get the first position of Red to put it there

 int posB=n-1; // Get the last Position to put Blue  there

while ( i < a.Length  )
{

   if (a[i]=='R') //try to put all RED in front
      {
        a[i] = a[posR];
        a[posR] = 'R';
        posR++;
      }
 
   if (a[i]=='B') //try to put all BLUE at the end
     {
       if (i < posB)
         {
              a[i] = a[posB];
              a[posB] = 'B';
              posB--; // 2nd last position for blue
              i--; // dec i incase the switched item is red
          }
      }

i++;
}


The above will not maintain the order. Say the sequence is:
{R1, B1, W1, B2} and posR = i = 0 and posB = 3

The iteration and state or array at each step is:
posR = 1 = i; posB = 3; {R1,B1,W1,B2}
posR = 1 = i; posB = 2; {R1,B2,W1,B1}
posR = 1 = i; posB = 1; {R1,W1,B2,B1}
posR = 1; posB = 0; i = 2; {R1,W1,B2,B1}

So, the final array becomes {R1,W1,B2,B1} while it should have been {R1,W1,B1,B2} (for it to be in sync with the original problem)

Quartz???


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board