CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

#### Hybrid View

1. Junior Member
Join Date
May 2011
Posts
1

## sort array

Is it possible to sort an array with n/2 1's and n/2 2's in 2n/3 comparisons?

2. ## Re: sort array

Why do you ask and what have you worked out so far?

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

4. Junior Member
Join Date
May 2011
Posts
22

## 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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•