[math-fun] Next generation sorting algorithm
I am please to inform you, math-fun, that I have developed the next generation sorting algorithm. I call it QUOBOSORT. Let me describe it. Randomly permute a list X until the minimum is in the first position of X. When this occurs, QUOBOSORT the rest of X until we reach an empty list. Here is the more formal algorithm. ALGORITHM --------- QUOBOSORT(X) := -- INPUT: a list of integers X -- OUTPUT: sorted X Q0. Is X an empty list? Yes: Return X. No : Go to Q1. Q1. Find the minimum M of X. Q2. Randomly permute X. Q3. Is M in the first position of X? Yes: Concatenate M and QUOBOSORT(REST(X)) No : Go to Q2. After one sorting iteration, the algorithm speeds up about N times! I hope you all are impressed. Sincerely, Robert Smith Inventor of QUOBOSORT
I'd like to suggest that you might supply some analysis of the performance before expecting entry to the marble halls of algorithmic recognition. Even if average or worst-case running times are presently too difficult, some numerical results on randomly unsorted lists (care required in generating these!) would lend a little credibility. WFL On 2/21/12, quad <quad@symbo1ics.com> wrote:
I am please to inform you, math-fun, that I have developed the next generation sorting algorithm. I call it QUOBOSORT.
Let me describe it. Randomly permute a list X until the minimum is in the first position of X. When this occurs, QUOBOSORT the rest of X until we reach an empty list.
Here is the more formal algorithm.
ALGORITHM ---------
QUOBOSORT(X) := -- INPUT: a list of integers X -- OUTPUT: sorted X
Q0. Is X an empty list? Yes: Return X. No : Go to Q1. Q1. Find the minimum M of X. Q2. Randomly permute X. Q3. Is M in the first position of X? Yes: Concatenate M and QUOBOSORT(REST(X)) No : Go to Q2.
After one sorting iteration, the algorithm speeds up about N times!
I hope you all are impressed.
Sincerely,
Robert Smith Inventor of QUOBOSORT
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* quad <quad@symbo1ics.com> [Feb 21. 2012 07:42]:
I am please to inform you, math-fun, that I have developed the next generation sorting algorithm. I call it QUOBOSORT.
[...]
http://en.wikipedia.org/wiki/Bogosort I think I have seen a variant that does even "better", namely doubly exponentially.
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 On Tue, Feb 21, 2012 at 2:01 AM, Joerg Arndt <arndt@jjj.de> wrote:
* quad <quad@symbo1ics.com> [Feb 21. 2012 07:42]:
I am please to inform you, math-fun, that I have developed the next generation sorting algorithm. I call it QUOBOSORT.
[...]
http://en.wikipedia.org/wiki/Bogosort
I think I have seen a variant that does even "better", namely doubly exponentially.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* 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
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
participants (5)
-
Fred lunnon -
Joerg Arndt -
quad -
Thomas Colthurst -
Victor Miller