Yeah, sorting "algorithms" generally require indexing. This web page relates to what you want, I believe. http://en.wikipedia.org/wiki/Sorting_network On Thu, Oct 1, 2009 at 8:22 PM, David Wilson <davidwwilson@comcast.net> wrote:
I'm not talking about an algorithm, but a fixed expression.
For example, an expression for the second smallest of 3 elements is
min(min(max(a, b), max(a, c)), max(b, c))
involving 6 variables (equivalently, 5 operations).
----- Original Message ----- From: "Joshua Zucker" <joshua.zucker@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Thursday, October 01, 2009 11:11 PM Subject: Re: [math-fun] minmax question
You can surely beat that by an awful lot, since sorting algorithms only take n lg n comparisons, and a comparison takes one min and one max. Or maybe I'm misunderstanding the question as usual.
If k is smallish, you can keep a list of the top k, and then to add each new element takes at most lg k comparisons, so that sounds like you can at least do it in (n-k) * lg k steps, which beats n lg n by a little.
--Joshua
On Thu, Oct 1, 2009 at 7:31 PM, David Wilson <davidwwilson@comcast.net> wrote:
Let f(n, k) be the number of binary min and max operations required to find the kth largest of n integers.
One way to find f(n, k) is to take the min over all of the maxes of subsets of k elements in A. This proves f(n, k) <= n C(n-1, k-1) - 1.
Is it possible to do better?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
--------------------------------------------------------------------------------
No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.409 / Virus Database: 270.14.1/2407 - Release Date: 10/01/09 06:34:00
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Check out Golly at http://golly.sf.net/