Prev: Best practices for configuration files
Next: How to (gu)estimate a software project duration?
From: pereges on 25 Jun 2008 01:27
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

int median( const intList * l ) {
for( int posn = 0; posn < l.size; posn++ )
int smaller = 0;
int larger = 0;
for( int p = 0; p < l.size; p++ )
if( l.items[p] < l.items[posn] )
smaller++;
else if( l.items[p] < l.items[posn] )
larger++;
if( smaller < l.size/2 && larger < l.size/2 )
return l.items[posn];
}
From: Willem on 25 Jun 2008 02:26
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


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
From: pete on 25 Jun 2008 07:09
pereges wrote:
> I have seen some code which can find median of an odd numbered list

What does it look like?

> but how to do it for even numbered list ? please give me some
> suggestions
>
> int median( const intList * l ) {
> for( int posn = 0; posn < l.size; posn++ )
> int smaller = 0;
> int larger = 0;
> for( int p = 0; p < l.size; p++ )
> if( l.items[p] < l.items[posn] )
> smaller++;
> else if( l.items[p] < l.items[posn] )
> larger++;
> if( smaller < l.size/2 && larger < l.size/2 )
> return l.items[posn];
> }

Copies of code are preferable to impressionistic drawings.

--
pete
From: Ben Bacarisse on 25 Jun 2008 07:55
pereges <Broli00(a)gmail.com> writes:

> 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
>
> int median( const intList * l ) {
> for( int posn = 0; posn < l.size; posn++ )
> int smaller = 0;
> int larger = 0;
> for( int p = 0; p < l.size; p++ )
> if( l.items[p] < l.items[posn] )
> smaller++;
> else if( l.items[p] < l.items[posn] )
> larger++;
> if( smaller < l.size/2 && larger < l.size/2 )
> return l.items[posn];
> }

This is probably re-typed. If the probable typos are corrected, we
get this:

int median(int n, const int *list)
{
for (int posn = 0; posn < n; posn++) {
int smaller = 0;
int larger = 0;
for (int p = 0; p < n; p++) {
if (list[p] < list[posn])
smaller++;
else if (list[p] > list[posn])
larger++;
}
if (smaller <= n/2 && larger <= n/2)
return list[posn];
}
}

This gives *an* answer, even for even-length arrays. Is it not the
answer you want? I say this because the usual mathematical definition
of median makes the answer rational (rather than integral) in some
cases which is often more trouble than it is worth. It depends
entirely on what you want the median for. Very often, the "middle
element" rather than the true median is what you really want.

On a more theoretical level, this is a quadratic solution to a linear
problem. In practical terms, the linear solutions are rather fiddly
and it is often better to opt for a O(n log(n)) solution like sorting
or a selection algorithm modelled on a sort (like quickselect).

--
Ben.
From: CBFalconer on 25 Jun 2008 09:51
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

list#1 = 1, 2, 3, 4
list#2 = 4, 5, 6, 7

I fail to see any difference in the median calculations for these.

This may be considered a foolish answer, but it is intended to
point out the inaccuracy in the original question.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **
 |  Next  |  Last
Pages: 1 2
Prev: Best practices for configuration files
Next: How to (gu)estimate a software project duration?