For worst-expected-time-but-still-deterministically-guaranteed-to-finish, I've always been fond of the following sorting algorithm: treat all of memory as one gigantic integer. At every step, increment that integer and then check if the high order bits are the input in sorted order. -Thomas C On Tue, Feb 21, 2012 at 10:07 AM, Joerg Arndt <arndt@jjj.de> wrote:
* Victor Miller <victorsmiller@gmail.com> [Feb 21. 2012 15:25]:
You should read the hilarious paper "Pessimal Algorithms and Simplexity Analysis" by Andrei Broder and Jorge Stolfi
http://www.cs.uiuc.edu/class/fa05/cs473ug/resources/pessimal-algorithms.pdf .
They have a strong definition of pessimal algorithm -- one that does badly even in the best case. So you have to work hard to avoid accidentally finding the right answer too soon. Their triumph is "slow sort". They get it from the standard quicksort program by only changing two lines. It is exponential in the best case (i.e. it takes exponential time even when the input is already sorted).
Victor
Lovely!
Thanks for the pointer, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun