Bogosort: a O(n.n!) sorting algorithm, Scheme implementation
Bogosort is a perversely awful algorithm [source]. Its awful because it is a direct fallout of the Infinite Monkey Theorem. Keep shuffling a set of numbers till it is sorted. That’s it. For a set of N numbers, you can have N! permutations and exactly one of them is the sorted. Now find that one. Wonderful.
Here is a Scheme implementation of Bogosort developed/tested it only with plt-scheme.I have used the “modern” Fisher-Yates shuffling algorithm for the shuffling exercise. The modern version has a O(n) time complexity versus the O(n^2) of the classic version.
And some more fun with a detailed analysis of perversely awful randomized sorting algorithms [link] and then there is Wikipedia
[…] of the Infinite Monkey Theorem. Bogosort is a sorting algorithm in that spirit. I had posted a Scheme implementation a while […]