Author |
Topic: Sort the array containing elements of three colors (Read 9756 times) |
|
cssomnath
Newbie
Posts: 20
|
 |
Sort the array containing elements of three colors
« on: Nov 10th, 2004, 10:29am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #1 on: Nov 10th, 2004, 10:44am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Sort the array containing elements of three co
« Reply #2 on: Nov 10th, 2004, 10:50am » |
Quote Modify
|
What I mean is in ONE PASS. Or execute the getColor() function on each element only once.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #3 on: Nov 10th, 2004, 12:05pm » |
Quote Modify
|
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]
|
| « Last Edit: Nov 14th, 2004, 1:01pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Sort the array containing elements of three co
« Reply #4 on: Nov 10th, 2004, 2:08pm » |
Quote Modify
|
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';
}
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #5 on: Nov 10th, 2004, 2:45pm » |
Quote Modify
|
It's easy enough to do with linear storage, at most I'd need to remember the color for three elements at a time.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
cssomnath
Newbie
Posts: 20
|
|
Re: Sort the array containing elements of three co
« Reply #6 on: Nov 11th, 2004, 8:18am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
tseuG
Junior Member
Gender:
Posts: 62
|
|
Re: Sort the array containing elements of three co
« Reply #7 on: Nov 11th, 2004, 12:01pm » |
Quote Modify
|
Right, you would just need to remember whether r has been changed, before entering the inner while loop to invoke getColor again.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Sort the array containing elements of three co
« Reply #8 on: Nov 11th, 2004, 11:01pm » |
Quote Modify
|
err this may sound stupid but can anyone give me an example of an input and expected output for this problem ??
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #9 on: Nov 12th, 2004, 3:47am » |
Quote Modify
|
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}
|
| « Last Edit: Nov 12th, 2004, 3:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
vikashkodati
Newbie
    
Gender:
Posts: 3
|
|
Re: Sort the array containing elements of three co
« Reply #10 on: Nov 14th, 2004, 12:05pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: Sort the array containing elements of three co
« Reply #12 on: Nov 23rd, 2004, 5:38pm » |
Quote Modify
|
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--
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
mamaheshwari
Newbie
Gender:
Posts: 2
|
|
Re: Sort the array containing elements of three co
« Reply #13 on: Dec 7th, 2004, 5:54am » |
Quote Modify
|
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--;
}
}
|
|
IP Logged |
|
|
|
Joe
Guest
|
|
Re: Sort the array containing elements of three co
« Reply #14 on: Dec 14th, 2004, 5:34am » |
Quote Modify
 Remove
|
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++;
}
}
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #15 on: Dec 8th, 2005, 12:15pm » |
Quote Modify
|
Seems a bit long for such a small problem..
|
| « Last Edit: Dec 8th, 2005, 12:34pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rene
Newbie
Gender: 
Posts: 28
|
|
Re: Sort the array containing elements of three co
« Reply #16 on: Dec 9th, 2005, 2:06pm » |
Quote Modify
|
another one with "one pass"
int temp,pos1,pos2,pos3,color1_initialised=0,color2_initialised=0,color3_ini tialsed=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
|
| « Last Edit: Dec 12th, 2005, 8:22pm by rene » |
IP Logged |
|
|
|
rene
Newbie
Gender:
Posts: 28
|
|
Re: Sort the array containing elements of three co
« Reply #17 on: Dec 11th, 2005, 8:28pm » |
Quote Modify
|
hello guys...... i am waiting eagerly for ur criticisms...
reply.. if the above algo is the best...... 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #18 on: Dec 12th, 2005, 1:24am » |
Quote Modify
|
You have a nested for-loop. Doesn't that make it slower than it has to be?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Sort the array containing elements of three co
« Reply #19 on: Dec 12th, 2005, 3:26am » |
Quote Modify
|
on Dec 11th, 2005, 8:28pm, 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 
|
|
IP Logged |
|
|
|
rene
Newbie
Gender:
Posts: 28
|
|
Re: Sort the array containing elements of three co
« Reply #20 on: Dec 12th, 2005, 8:28pm » |
Quote Modify
|
thank u towr and johanc;
i have modified the code for better readability
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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sort the array containing elements of three co
« Reply #21 on: Dec 13th, 2005, 2:40am » |
Quote Modify
|
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.
|
| « Last Edit: Dec 13th, 2005, 2:50am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Quartz
Newbie
Gender:
Posts: 11
|
|
Re: Sort the array containing elements of three co
« Reply #22 on: Feb 8th, 2007, 5:02pm » |
Quote Modify
|
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++;
}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sort the array containing elements of three co
« Reply #23 on: Feb 9th, 2007, 3:08am » |
Quote Modify
|
You could do while ( i <= posB ) ...
|
|
IP Logged |
|
|
|
Quartz
Newbie
Gender:
Posts: 11
|
|
Re: Sort the array containing elements of three co
« Reply #24 on: Feb 9th, 2007, 9:22am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print