-
May 16th, 2011, 09:19 PM
#1
sort array
Is it possible to sort an array with n/2 1's and n/2 2's in 2n/3 comparisons?
-
May 16th, 2011, 11:48 PM
#2
Re: sort array
Why do you ask and what have you worked out so far?
Best Regards,
BioPhysEngr
http://blog.biophysengr.net
--
All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.
-
May 17th, 2011, 01:32 AM
#3
Re: sort array
If you *KNOW* there are exactly n/2 1's and n/2 2's, then why sort ?
Go over the array and assign 1 to the first n/2 elements and 2 for the rest.
Exactly n assignments and no need for comparison...
Regards,
Zachm
-
May 17th, 2011, 11:35 AM
#4
Re: sort array
Hi
if you mean it theoretical, if it is possible to describe an array out of n/2 1's and n/2 0's with 2n/3 bits of Information (2n/3 decisions), then the answer is "no", because n over n/2 is always greater than 2^(2n/3).
Greetings, Marco
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|