Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6898

Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes)

Show all headers | View raw

On Monday, August 22, 2016 at 8:27:50 AM UTC+1, malcolm...@btinternet.com wrote:
> On Sunday, August 21, 2016 at 10:08:50 PM UTC+1, Öö Tiib wrote:
> > On Saturday, 20 August 2016 04:08:07 UTC+3, malcolm...@btinternet.com  wrote:
> > > On Friday, August 19, 2016 at 11:38:31 PM UTC+1, Ben Bacarisse wrote:
> > > > Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> > > > 
> > > > > Malcolm McLean <malcolm.mclean5@btinternet.com> writes:
> > > > >
> > > > >> On Friday, August 19, 2016 at 3:46:01 PM UTC+1, Ben Bacarisse wrote:
> > > > >>>
> > > > >>> The O(N log N) method using binary search sounds odd -- the description
> > > > >>> does not seem to match any selection algorithm I know.  Can you explain
> > > > >>> what you meant?
> > > > >>> 
> > > > >> Pass through the data, taking maximum and minimum. Then use (max +
> > > > >> min)/2 as you first guess for the median. Pass through again counting
> > > > >> elements above and below, and the nearest in both directions. If you
> > > > >> are wrong, use (max (or min) + guess)/2 as your refined guess and
> > > > >> repeat, doing a binary search.
> > > > >> If you are right, the nearest rather than the guess is the answer.
> > > > >
> > > > > Interesting.  I did not know that one.  Maybe the fact that it's not
> > > > > linear time makes people overlook it, but there must be times when
> > > > > neither copying nor rearranging the array is acceptable.
> > > > >
> > > > > A bit more searching suggests that some people call this Torben's
> > > > > algorithm.  Do you know the inventor or simply a definite name for it?
> > > > 
> > > > That's a first name and probably not that of the originator.  Does
> > > > anyone know more about it?
> > > > 
> > > > (I've changed the subject and set Followup-To: comp.programming.)
> > > > 
> > > The algorithm was invented by me, and independently by Torben Mogenson,
> > > and probably by many other people as well.
> > 
> > AFAIK he is Mogensen, not Mogenson. They likely call it "Torben's
> > algorithm" to avoid embarrassment of misspelling the last name of
> > author. ;D
> .
> Anyway, I've consulted with the bulging brains on Math Exchange,
> and the median may not be more than one standard deviation away
> from the mean.
> So we can implement a more efficient search. It won't totally
> solve the problem of data with an exponential-logarithmic 
> distribution, but it will substantially alleviate it.

This is the first draft.

double medianbs(const double *x, int N)
{
	double mean = 0.0;
	double	M2 = 0.0;
	double delta;
	double sd;
	int i;
	int less, greater, equal;
	double  minx, maxx, guess, maxltguess, mingtguess;
	double answer;
	int Npasses = 0;

	if (N == 0)
		return 0;
	if (N == 1)
		return x[0];
	if (N == 2)
		return (x[0] + x[1]) / 2;

	for (i = 0; i < N; i++)
	{
		delta = x[i] - mean;
		mean += delta / (i + 1);
		M2 += delta*(x[i] - mean);
	}
	sd = sqrt(M2 / (N -1));

	minx = mean - sd;
	maxx = mean + sd;

	while (1) {
		guess = (minx + maxx) / 2;
		less = 0; greater = 0; equal = 0;
		maxltguess = minx;
		mingtguess = maxx;
		for (i = 0; i<N; i++) {
			if (x[i]<guess) {
				less++;
				if (x[i] > maxltguess)
					maxltguess = x[i];
			}
			else if (x[i]>guess) {
				greater++;
				if (x[i] < mingtguess)
					mingtguess = x[i];
			}
			else equal++;
		}
		if (less <= (N + 1) / 2 && greater <= (N + 1) / 2) 
			break;
		else if (less>greater) maxx = maxltguess;
		else minx = mingtguess;
	}

	if (equal == 0)
	{
		if (less == greater)
			answer = (maxltguess + mingtguess) / 2;
		else if (less > greater)
			answer = maxltguess;
		else
			answer = mingtguess;
	}
	else
	{
		if (less == (N + 1) / 2)
			answer = maxltguess;
		else if (less + equal >= (N + 1) / 2)
		{
			if ((N % 2))
				answer = guess;
			else
			{
				if (less == N / 2)
					answer = (maxltguess + guess) / 2;
				else if (greater == N / 2)
					answer = (mingtguess + guess) / 2;
				else
					answer = guess;
			}
		}
		else
			answer = mingtguess;
	}

	return answer;
}

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-08-19 23:38 +0100
  Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) malcolm.mclean5@btinternet.com - 2016-08-19 18:08 -0700
    Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) Öö Tiib <ootiib@hot.ee> - 2016-08-21 14:08 -0700
      Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) malcolm.mclean5@btinternet.com - 2016-08-22 00:27 -0700
        Re: O(n log n) in place median algorithm (was: Difference between these pointer syntaxes) malcolm.mclean5@btinternet.com - 2016-08-22 19:31 -0700

csiph-web