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/

Sorting networks are close to what I want, but not quite. A sorting network can be used to generate a min/max expression for the nth element. If we are sorting n elements a_1 through a_n, initialize strings e_1 through e_n to "a_1" through "a_n" respectively. Then when the network sorts a_i and a_j (i < j), set (e_1, e_j) <- ("min(" || e_i || "," || e_j || ")" , "max(" || e_i || "," || e_j || ")") where || is concatenation. When the network finishes, e_k will hold the min/max expression for the kth sorted element in terms of the original elements. If we are merely interested in counts, initialize list v_1 through v_n each to 1. When the network sorts a_i and a_j, replace each of v_i and v_j with v_i + v_j. When the network is finished, v_k gives the number of variables in the min/max expression e_k for the kth sorted element, and v_k - 1 gives the number of min/max operations in e_k. There is a 4-element (n = 4) sorting network illustrated at the beginning of the suggested Wiki article. If we compute the e_i and v_i for this network, we get e_1 = "min(min(a_1,a_3),min(a_2,a_4))" e_2 = "min(max(min(a_1,a_3),min(a_2,a_4)),min(max(a_1,a_3),max(a_2,a_4)))" e_3 = "max(max(min(a_1,a_3),min(a_2,a_4)),min(max(a_1,a_3),max(a_2,a_4)))" e_4 = "max(max(a_1,a_3),max(a_2,a_4))" with variable counts v_1 = 4 v_2 = 8 v_3 = 8 v_4 = 4 My apparently crude upper bound was v_k = n C(n-1, k-1), where the kth sorted element is obtained by taking the min over the maxes of every k-element subset. This gives v_1 = 4 v_2 = 12 v_3 = 12 v_4 = 4 So this particular sorting network beats my expression for the 2nd and 3rd sorted element out of 4. On the other hand, a 3-element sorting network (n = 3) must involve 3 sorts. Sorting elements ((a_1, a_2), (a_1, a_3), (a_2, a_3)) gives expressions e_1 = "min(min(a_1,a_2),a_3)" e_2 = "min(max(a_1,a_2),max(min(a_1,a_2),a_3))" e_3 = "max(max(a_1,a_2),max(min(a_1,a_2),a_3))" with v_1 = 3 v_2 = 5 v_3 = 5 whereas my upper bound is v_1 = 3 v_2 = 6 v_3 = 3 So this network generates a better expression for the 2nd element, but a worse for the 3rd. We could use the network's results to generate a better expression for e_3, namely e_3 = "max(max(a_1,a_2), a_3)" by min/max swapping on e_1, however, no 3-element sorting network simultaneously generates optimal expressions for both e_1 and e_3. So minimal sorting networks sometimes do better than my naive approach, but I don't think they necessarily generate optimal expressions, since they are interested in sorting all the elements, not simply finding the kth element. ----- Original Message ----- From: "Joshua Zucker" <joshua.zucker@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Friday, October 02, 2009 12:37 AM Subject: Re: [math-fun] minmax question

On Thu, Oct 1, 2009 at 8:25 PM, Tom Rokicki <rokicki@gmail.com> wrote:

...

Yeah, sorting "algorithms" generally require indexing.

This web page relates to what you want, I believe.

http://en.wikipedia.org/wiki/Sorting_network

And then maybe these sequences are of some use: http://tinyurl.com/OEISsort (link to OEIS)

--Joshua

_______________________________________________ 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