Sorting (Part 4.0): Bogo Sort & Wasting Time

So DTM insisted I write up a little article on Bogo Sort.

What Is Bogo Sort?

Bogo Sort is a sorting algorithm that is not used in production at all. Why? Because it's extremely stupid. Some even call it "Stupid Sort."

The algorithm works by generating random permutations of an inputted array-to-sort. Then, it checks to see if the randomly generated permutation is sorted. If so, it returns that sorted array and exits; otherwise, it makes another permutation.

Worst-Case Time Complexity: O( (n+1)! ) because of all the possible permuting.

Best-Case Time Complexity: O(n) if the array-to-sort is already sorted.

Note: Bogo Sort can generate the same permutation more than once in a run, thus wasting even more of our time.

Ruby Implementation

Here you can find my Ruby implementation of Bogo Sort. You can also refer to this screenshot:

I'll tell you that I got inspiration for this implementation from various parts of the internet -- and probably Wikipedia.

So, anyway, I've extended Ruby's Array class to have a few extra methods: sorted? and bogosort.

I hope that you all can infer what sorted? does; yet, if not, I'll tell you that it ensures that all the elements are in order.. and, yes, I'm that guy who uses for loops in Ruby.

Okay, so bogosort basically just uses a built-in shuffle method to get a new permutation of the array-to-sort and stops shuffling when the array-to-sort is sorted. Simple enough.

C++ Version

Find the C++ source here or see the picture below:

The deal is the same for is_sorted(...) as it was for our Ruby implementation's sorted?.

In our C++ implementation, however, I actually define my own shuffle function. Basically, it swaps an element in our vector/array with another, randomly-chosen one to create a fresh permutation. Of course, it could potentially do the same thing twice.

The actual bogosort(...) function does the same thing in this C++ version as our Ruby version did.

Conclusion

That's it for Bogo/Stupid/Monkey Sort.

You can check out this cool Stack Overflow post for some more crazy sorting algorithms.

Leave a comment if you have a question.

See you all later,

oaktree