CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: sort array

  1. #1
    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. #2
    Join Date
    Feb 2011
    Location
    United States
    Posts
    1,016

    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.

  3. #3
    Join Date
    Oct 2006
    Posts
    616

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

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
  •  





Click Here to Expand Forum to Full Width

Featured