Re: Algorithm for finding Median: Got one or can you dissect this?

[Paul E. Johnson]

"Marcus G. Daniels" wrote:
> 
> >>>>> "PJ" == Paul E Johnson <address@hidden> writes:
> 
> PJ> If you have a nice, quick algorithm to find medians, please give it to
> PJ> me, because I've tried pretty hard with this one.
> 
> Fundamentally, it should be possible to QSort an array copy of
> a collection an then do:
> 
>   lhs = (n - 1) / 2;
>   rhs = n / 2;
> 
>   if (n == 0)
>     return 0.0;
> 
>   if (lhs == rhs)
>     median = (lhs == rhs) ? sorted[lhs] : (sorted[lhs] + sorted[rhs]) / 2.0;
> 
> Sorry, SwarmFest pressures prevent me from looking at your test case now.
> 
>                   ==================================
Thanks for looking.  I've already succeeded using qsort.  

WHen you don't need to sort a whole array, but just pick a median point,
there are algorithms that are much faster, or at least Numerical Recipes
says so. Of course, their algorithm is screwed up.  But I know from
experience that there are faster ways than qsorting, I just don't have
the code for the best way..

So if one of you computer professors/students has a working selection
algorithm, I'd still like to see it.

-- 
Paul E. Johnson                         email: address@hidden
Dept. of Political Science              http://lark.cc.ukans.edu/~pauljohn
University of Kansas                    Office: (785) 864-9086
Lawrence, Kansas 66045                  FAX: (785) 864-5700

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.