Author |
Topic: Another Sorting Problem (Read 1397 times) |
|
dante
Newbie
Posts: 34
|
 |
Another Sorting Problem
« on: Jun 21st, 2007, 8:56pm » |
 Quote  Modify
|
Given an array whose each element can have only one of 3 unique values.Sort it in o(n).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Another Sorting Problem
« Reply #1 on: Jun 22nd, 2007, 12:44am » |
Quote Modify
|
Well, if there's onyl three values, you can just count the number of each, then put in as many copies as there need to be.
On the other hand if they're three classes (and thus aren't identical and can't be replaced by copies) You can just consider insertion sort, and that shifting a section of one class by one position is equivalent to moving it's first element behind it's last, which means it only costs constant time to "shift". In fact, O(n) sorting is possible whenever you have an upper limit to the number of distinct values/classes.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #2 on: Jun 22nd, 2007, 12:59am » |
Quote Modify
|
No classes only values
Counting the no of each value requires 1 traversal
and assigning requires another traversal
I think its O(2n)
am not good at finding complexity .. point out if am wrong ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another Sorting Problem
« Reply #3 on: Jun 22nd, 2007, 2:56am » |
Quote Modify
|
on Jun 22nd, 2007, 12:59am, dante wrote:
O(2n)=O(n)
A constant factor does not matter to the complexity. (Although, of course it may matter in practice)
Quote:Well, then it's not very interesting; as just counting suffices. Heck, why even bother having multiple of the same elements in an array, just keeping a count for each is a much more efficient representation.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #4 on: Jun 22nd, 2007, 6:49am » |
Quote Modify
|
The real question specifies to do the sort in exactly O(n)
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Another Sorting Problem
« Reply #5 on: Jun 22nd, 2007, 7:00am » |
Quote Modify
|
Sounds familiar, only last time it was colors...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #6 on: Jun 22nd, 2007, 9:18am » |
Quote Modify
|
Thanx for pointing out the thread ... In that problem you know the 3 unique values (R,W,B).. here you are not given the 3 unique values ...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another Sorting Problem
« Reply #7 on: Jun 24th, 2007, 7:57am » |
Quote Modify
|
on Jun 22nd, 2007, 9:18am, dante wrote:| Thanx for pointing out the thread ... In that problem you know the 3 unique values (R,W,B).. here you are not given the 3 unique values ... |
|
You may as well; you have the first "color" you encounter, the second "color" you encounter and the last. You can even call them A,B,C.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #8 on: Jun 24th, 2007, 11:24am » |
Quote Modify
|
Well this is the code I have written ... am not sure of its working ... I have tested it as far as possible ....
| hidden: | swap (int *p,int *q)
{
int t=*p;
*p=*q;
*q=t;
}
int main()
{
int *a,n,*r,t,i;
int start = 0,end ;
int j=0;
// input the no of elements in the array
scanf("%d",&n);
a =(int *)malloc(n*sizeof(int));
end = n-1;
//input the elements
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<end;i++)
{
t=0;
if(a[0]> a[i])
{
start = 0;
swap(&a[i],&a[0]);
t=1;
}
else if(a[0]== a[i] && i >start+1)
{
start++;
swap(&a[i],&a[start]);
}
r=&a[i];
if(t)
r = &a[start];
if(a[n-1] <*r)
{
end = n-1;
swap(r,&a[end]);
}
else if(a[n-1]==*r && i<end-1)
{
end--;
swap(r,&a[end]);
i--;
}
}
for(j=0;j<n;j++)
printf("%d\n",a[j]);
printf("\n");
getch();
} |
|
|
IP Logged |
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #9 on: Jun 24th, 2007, 11:26am » |
Quote Modify
|
I would like to see some small sized code for this problem ... 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another Sorting Problem
« Reply #10 on: Jun 24th, 2007, 12:55pm » |
Quote Modify
|
I haven't added the reading and swapping code. And it's a bit compressed at places. But if I haven't made any errors it should just about work..
Code:int l,m,r;
for(l=1; l < n && a[l]==a[0]; l++);
for(m=l+1; m < n && a[m]==a[l] ; m++);
for(r=m; r < n; r++)
{
if(a[r] == a[0]) // if next element is equal to the first type
swap(&a[l++],&a[r]);
if(a[r] == a[l]) // if next element is (now) equal to the second type
swap(&a[m++],&a[r]);
}
|
|
The last bit could be a bit better, althought it's less legible:
Code:
for(r=m; r < n; r++)
((a[r] == a[0] && swap(&a[l++],&a[r])) || a[r] == a[l]) && swap(&a[m++],&a[r]);
|
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #11 on: Jun 24th, 2007, 10:33pm » |
Quote Modify
|
Checked your code with n=6
1 3 2 2 3 1
the output was
1 1 3 3 2 2
And towr am not sure whether its exactly O(n)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another Sorting Problem
« Reply #12 on: Jun 25th, 2007, 1:32am » |
Quote Modify
|
on Jun 24th, 2007, 10:33pm, dante wrote:Checked your code with n=6
1 3 2 2 3 1
the output was
1 1 3 3 2 2 |
|
All classes are seperated, I call that sorted.
I suppose if you assume an ordering between the unknown values, you could amend the algorithm to take that into account.
Removing the second for-loop (which is just for speeding things up anyway; actually so is the first) and changing "==" to "<=" in the third might possibly do it..
Quote:| And towr am not sure whether its exactly O(n) |
|
There are only single loops, how could it not be?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #13 on: Jun 25th, 2007, 1:53am » |
Quote Modify
|
yeah there are only single loops but not even solution of O(2n) is acceptable ... I mean the constant factor is not to be ignored here ... This is how my friend gave the problem ... I dont know how far its practically significant
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Another Sorting Problem
« Reply #14 on: Jun 25th, 2007, 2:55am » |
Quote Modify
|
on Jun 25th, 2007, 1:53am, dante wrote:| yeah there are only single loops but not even solution of O(2n) is acceptable ... I mean the constant factor is not to be ignored here ... This is how my friend gave the problem ... I dont know how far its practically significant |
|
Well O(2n)=O(n), but even disregarding that, I'm not going through the array twice or thrice, but just once.
For each for-loop the index picks up where the previous one left off.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
I_am_searching
Newbie
Gender:
Posts: 30
|
|
Re: Another Sorting Problem
« Reply #15 on: Jun 25th, 2007, 8:33am » |
Quote Modify
|
say we have three numbers R,G,B(this we store in variables and are only stored as and when they are encountered while traversng the array.)
Now i have thrre different varibales that keep the information of the
1.current begin index for second largest number
2.current end index for second largest number
3. current begin index of third largest number
I try to move smallest number to the begining of array
I try to move the largets number to the end of array
these two are done by mere swapping.
and finally i get the array with smallest elemts in begining. second larget in middle and the largest in the end.
stil working on the code.
towr need ur inputs 
|
|
IP Logged |
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #16 on: Jun 25th, 2007, 9:44am » |
Quote Modify
|
Sorry for overlooking it
|
|
IP Logged |
|
|
|
dante
Newbie
Posts: 34
|
|
Re: Another Sorting Problem
« Reply #17 on: Jun 25th, 2007, 9:55am » |
Quote Modify
|
on Jun 25th, 2007, 8:33am, I_am_searching wrote:say we have three numbers R,G,B(this we store in variables and are only stored as and when they are encountered while traversng the array.)
Now i have thrre different varibales that keep the information of the
1.current begin index for second largest number
2.current end index for second largest number
3. current begin index of third largest number
I try to move smallest number to the begining of array
I try to move the largets number to the end of array
these two are done by mere swapping.
and finally i get the array with smallest elemts in begining. second larget in middle and the largest in the end.
stil working on the code.
towr need ur inputs |
|
My code above exactly does that
|
|
IP Logged |
|
|
|
anshulk_scorp
Newbie
Posts: 8
|
|
Re: Another Sorting Problem
« Reply #18 on: Jun 27th, 2007, 9:57pm » |
Quote Modify
|
I guess this is a variation of Quick Sort.
This can be done in a single iteration of the array.
Take two iterators from both ends.
If fwd iterator points to 0 (smallest)
increment it.
else If bkwrd iterator points to 2 (largest)
decrement it.
else
{
note the ordered pair
if it is 2,0 swap them and stepup the iterators.
(If all condittions were implemented carefully....iterators will stop only at point whre ordered pair is 1,1.)
In this case.Introduce a third iterator mid starting at point where fwd iterator stopped.
if mid is 1,step it up until 0 or 2 is found.
if mid is 0,swap the value with fwd iterator and repeat the above steps.
if mid is 2,swap the value with bkwd iterator and repeat the above steps.
}
|
|
IP Logged |
|
|
|
anshulk_scorp
Newbie
Posts: 8
|
|
Re: Another Sorting Problem
« Reply #19 on: Jun 27th, 2007, 10:33pm » |
Quote Modify
|
The following example will illustrate this...
Consider:
0 0 1 0 2 1 2 0 1 2 0 2 2
Step 1: fwd is at 0 bkwd is at 2.Step up both.
Step 2: Again 0,2 step up both
Step 3: Bkwd at 0 swap with fwd.Step up fwd only.
0 0 0 0 2 1 2 0 1 2 1 2 2
Step 4: 0,1 step up fwd only
Step 5: 2,1 swap them and step up backward only.
0 0 0 0 1 1 2 0 1 2 2 2 2
Step 6: 1,1
introduce mid.
Step 7: mid = 1 Step it.
0 0 0 0 1 1 2 0 1 2 2 2 2
Step 8: mid = 2 Swap with Bkwd and stepup bkwd only.(Mid loses its scope now)
0 0 0 0 1 1 1 0 2 2 2 2 2
Step 9: 1,0 .Swap them.Step up fwd.
0 0 0 0 0 1 1 1 2 2 2 2 2
Step 10: 1,1. Introduce mid.
0 0 0 0 0 1 1 1 1 2 2 2 2
mid=1.Step it
Step 11:iterator collision.Array is sorted.
0 0 0 0 0 1 1 1 2 2 2 2 2
|
|
IP Logged |
|
|
|
aki_scorpion
Newbie
Gender:
Posts: 13
|
|
Re: Another Sorting Problem
« Reply #20 on: Jul 7th, 2007, 10:26am » |
Quote Modify
|
anshulk :
Nice solution and u did maintain O(n) ... though u might have some extra constant due to the introduction of mid .. Please take into that into consideration.
Please consider the case of all 1's ..  .. I am not able to get through that.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print