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.
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...
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).
Reply With Quote
Bookmarks