Author |
Topic: Sort the array containing elements of three colors (Read 9715 times) |
|
msaha
Newbie
Gender: 
Posts: 4
|
 |
Re: Sort the array containing elements of three co
« Reply #25 on: Aug 6th, 2010, 1:09pm » |
 Quote  Modify
|
on Feb 8th, 2007, 5:02pm, 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
|
|
 IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print