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

[Theodore C. Belding]

Hi-
Here are some references for selection algorithms or finding medians, in
order of accessibility.

Sedgewick, Robert. (1998). Algorithms in C. Third Edition. Parts 1-4.
Addison-Wesley. ISBN 0-201-31452-5. pp. 329-333.

Knuth, Donald E. (1998). The Art of Computer Programming. Volume 3:
Sorting and Searching. Second Edition. Addison-Wesley. ISBN
0-201-89685-0. pp. 207-216.

Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. (1990).
Introduction to Algorithms. MIT Press. ISBN 0-262-03141-8. Chapter 10. pp.
185-194.

Have fun.
-Ted

--
Ted Belding                               address@hidden 
University of Michigan Program for the Study of Complex Systems
Homepage: http://www-personal.umich.edu/~streak/
PGP key:  http://www-personal.umich.edu/~streak/pgp-key.html

On Mon, 22 Mar 1999, Paul E. Johnson wrote:

> "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.
> 



                  ==================================
   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.