Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Ben Bacarisse 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> References: <87bn0rut34.fsf@bsb.me.uk> <9283b112-8250-4e0b-b149-6ca728a3200b@googlegroups.com> <07faa95e-2470-4375-93e9-15e79ee4e0e4@googlegroups.com> <55578778-4482-458e-b43d-b763732c0054@googlegroups.com> <87mvkas5gb.fsf@bsb.me.uk> <87a8g9r73i.fsf@bsb.me.uk> <20feb7cc-77d8-4ffe-b12b-42c5b2025afb@googlegroups.com> <874m6gq49x.fsf@bsb.me.uk> <3089ee96-fae7-4317-bb03-cfc7775d9afa@googlegroups.com> <87r39kolzz.fsf@bsb.me.uk> <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 Ben Bacarisse writes: > Malcolm McLean 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.