Bogosort is obviously not well designed, as it has a data conditioning problem -- its best and worst cases are dramatically different given only data in the wrong order. That can be easily resolved by moving the comparison to the end of the loop instead of the beginning, so you perform one randomization before checking for ordered data. This way there's no way the state of the input data can make the algorithm worse. (Quicksort has a similar problem.)
Whew. I don't know what they teach in these schools these days. There's a hidden problem with randomness -- if you're using a PRNG you have to be careful about how you generate the permutations, since your number of permutations can exceed the RNG's period. http://stackoverflow.com/questions/3062741/maximal-length-of-list-to-shuffle-with-python-random-shuffle If you need to sort 3000 elements it might make a difference between getting the answer after the total heat-death of all possible universes, and never getting the answer at all. -Wm On Sat, Dec 28, 2013 at 5:07 PM, Raul Miller <[email protected]> wrote: > Here is a rather awful sorting algorithm: > > http://www.dangermouse.net/esoteric/bogobogosort.html > > For reference, here's a reasonably close to canonical definition of > big-O notation: > > http://en.wikipedia.org/wiki/Big_O_notation > > the above algorithm was suggested on another mailinglist during a > discussion of this code competition: > http://codegolf.stackexchange.com/questions/16226/trolling-homework-questions-sorting > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
