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

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c, comp.programming
Subject	O(n log n) in place median algorithm (was: Difference between these pointer syntaxes)
Followup-To	comp.programming
Date	2016-08-19 23:38 +0100
Organization	A noiseless patient Spider
Message-ID	<87oa4omljv.fsf_-_@bsb.me.uk> (permalink)
References	(16 earlier) <874m6gq49x.fsf@bsb.me.uk> <3089ee96-fae7-4317-bb03-cfc7775d9afa@googlegroups.com> <87r39kolzz.fsf@bsb.me.uk> <f8b4c402-83db-4044-ba66-6472cb3b402e@googlegroups.com> <87fuq0ohw8.fsf@bsb.me.uk>

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show all headers | View raw

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

-- 
Ben.

Back to comp.programming | Previous | Next — Next 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