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

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
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	Fri, 19 Aug 2016 23:38:28 +0100
Organization	A noiseless patient Spider
Lines	31
Message-ID	<87oa4omljv.fsf_-_@bsb.me.uk> (permalink)
References	<nodpg5$cr7$1@dont-email.me> <bbe84ac6-290d-4f17-97e5-ddaceaac6e49@googlegroups.com> <np23e0$oos$1@dont-email.me> <87bn0rut34.fsf@bsb.me.uk> <np2equ$2p2$1@dont-email.me> <9283b112-8250-4e0b-b149-6ca728a3200b@googlegroups.com> <np2iei$frm$1@dont-email.me> <07faa95e-2470-4375-93e9-15e79ee4e0e4@googlegroups.com> <np2pk0$9lm$1@dont-email.me> <55578778-4482-458e-b43d-b763732c0054@googlegroups.com> <87mvkas5gb.fsf@bsb.me.uk> <a853c5fa-c270-4837-8b9e-1e6ecc26478e@googlegroups.com> <np4agt$a89$1@dont-email.me> <87a8g9r73i.fsf@bsb.me.uk> <20feb7cc-77d8-4ffe-b12b-42c5b2025afb@googlegroups.com> <np6u1u$kcs$1@dont-email.me> <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>
Mime-Version	1.0
Content-Type	text/plain
Injection-Info	mx02.eternal-september.org; posting-host="017616aa25f81ec581c44d76d61ba2f3"; logging-data="20414"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/NXcRRNDRONjurCopKWPxBsprYxmUpctY="
Cancel-Lock	sha1:+C2oUVQkxfM39e1cgmRUFrIFrcg= sha1:NBFsFZsfAFdutcdjj/eH3ip/WG4=
X-BSB-Auth	1.27c07637db5ef974e1c9.20160819233828BST.87oa4omljv.fsf_-_@bsb.me.uk
Xref	csiph.com comp.lang.c:92520 comp.programming:6891

Cross-posted to 2 groups.

Followups directed to: comp.programming

Show key headers only | 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