Mathematics desk
< October 7	<< Sep \| October \| Nov >>	October 9 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

October 8

Minimizing first-time comparisons

What's the best sorting algorithm that minimizes the number of first-time comparisons? This generally involves data that is expensive to initially compare (or otherwise can't be algorithmically compared), but once the initial comparison is made, the result can be cached.

After a new comparison is made, my system looks for things similar to A < B < C and ensures that A < C. It then searches the cache to find which pair eliminates the most combinations. Even though this works, I feel this may be the bottleneck, since a full search (probably O(n^4+)) could make the sorting much longer than it could, and a limited search (currently O(n^3)) may be less accurate.

I'm aware of a monte-carlo algorithm, but I'm not sure whether to go for that or the full-search in the comparison matrix. --Sigma 7 (talk) 02:29, 8 October 2008 (UTC)[reply]

If the elements are in random order initially then you can't really beat a good standard sort by anything significant for smallest average number of comparisons. The Comparison sort article also mentions that 42 is the least maximum number of comparisons needed for 15 items, I don't know if it is best on average though - some hand crafted algorithm like this could be used in the middle of another sort to improve it slightly - about five is as much as people deal with specially normally. Dmcq (talk) 08:41, 8 October 2008 (UTC)[reply]

Merge sort comes very close to the lower bound on the number of comparisons. It uses n ceiling(log₂n) - n + 1 comparisons, while the comparison tree lower bound is approximately n log₂n - 1.4427 n comparisons. It's not optimal, but it's straightforward and good. —David Eppstein (talk) 17:07, 9 October 2008 (UTC)[reply]

The Ford-Johnson algorithm mentioned in the article on comparison sorts is a kind of merge sort, not very efficient internally but very close to optimal in the number of comparisons. Dmcq (talk) 17:36, 9 October 2008 (UTC)[reply]

Possible to solve this calculus problem?

I saw [1] on Uncyclopedia and I was wondering if it really could be solved.

Can it? (If you take out the Tuesday thing) What if you substituted values?

Would anybody be willing to solve it? (You can use your own units or whatever) Or is it lacking vital information for that?

~Cheers!~ User: ECH3LON

P.S. -If this would be considered "spam", I apologize, just ignore it if that's the case :) —Preceding unsigned comment added by ECH3LON (talk • contribs) 23:46, 8 October 2008 (UTC)[reply]

I think the 'problem' is pretty obviously a joke, as might be expected given the source. AndrewWTaylor (talk) 09:36, 9 October 2008 (UTC)[reply]

The problem is complete nonsense, it's just a random sequence of mathematical words, they have no meaning in that combination. --Tango (talk) 10:30, 9 October 2008 (UTC)[reply]

I don't know. I found a really complicated quantum physics equation on Uncyclopedia one day. It's in my sandbox if you would like to see. :) Ζρς ι'β' ^¡hábleme! 21:32, 9 October 2008 (UTC)[reply]

A lengthy discussion on that very equation is in the ref desk archives (maths, I think, possibly science)! Just because that's a genuine equation doesn't mean "Matrix the antiderivative to the sixth power where needed" has any actual meaning. :) --Tango (talk) 22:04, 9 October 2008 (UTC)[reply]

Yep, science archives. Oh, I know that thing doesn't have any real meaning, I was just saying that there are some legitimate things on Uncyclopedia. Ζρς ι'β' ^¡hábleme! 22:19, 9 October 2008 (UTC)[reply]