Bogosort: a O(n.n!) sorting algorithm, Scheme implementation

by Amit


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

Advertisements