Re: finding the median of a list without sorting

On Jun 28, 7:30 pm, Ben Bacarisse <ben.use...@xxxxxxxxx> wrote:
Gene <gene.ress...@xxxxxxxxx> writes:
On Jun 25, 2:26 am, Willem <wil...@xxxxxxxx> wrote:
pereges wrote:

) I have seen some code which can find median of an odd numbered list
) but how to do it for even numbered list ? please give me some
) suggestions

First, try to figure out exactly what 'the median of an even sized list'
means.

What is the median of this list:  1 2 3 4
<sig snipped>

Every prob and stats book I've ever seen would say 2.5, i.e. the
arithmetic mean of the two middle elements.

There are some that don't, although every one I've seen eventually
suggests picking the mean of the two as a "practical" solution.  All
the technical definitions that I can find say that median of that
sample is not unique.

For algorithms it is often *not* practical to take the mean of the two
middle values: the mean may be of different type to the sample data
(e.g. a rational rather than an integer) or, worse, the mean may not
be well-defined.  The median string of the set {"a", "b", "c"} is "b",
but what would we choose for the median of {"a", "b", "c", "d"} using
the conventional "mean of the two middle values" answer[1]?

Since the technical definitions all include both endpoints of the range
bounded by the two middle elements we can choose either end.  This is
the practical answer in CS.


The practical CS answer is to return the middle pair and punt the
decision to the caller!
.