The CS department recently finished our new building, and it's the first time I've actually been seated with my fellow labmates. As the first item of business, we commenced prototyping our own version of Bogosort.
According to Wikipedia, the expected runtime is (n - 1) n!, so obviously we sought to empirically determine if this was accurate. Our results showed that for lists of length 10, the number of iterations varied wildly from 1.0 to 315.9% the expected number of iterations, with an average at around 82.8%. We also found that, for lists of numbers of length 15, nobody had the patience to wait for a single run to finish. We also empirically determined Python is inefficient and hypothesized that C++ could probably even do the job better.
If you'd like to run the code yourself, you can find it here.
And finally, we determined an even more "efficient" (I use the term loosely, since efficiency for Bogosort is somewhat of a misnomer) Bogosort algorithm:
While not sorted(list): Rebuild Universe
Unfortunately, we never made it past the prototyping stage, even after expanding our search to include non-standard libraries.
No comments:
Post a Comment