Bogo sort, you must be joking ?

Slow runtimes are no laughing matter Mr. Joker sir !

In my endless quest to become a better developer, I spent some time looking over algorithms. Many are very useful and I’ve often have used them for years without even realizing of their existence or importance! I figured every algorithm was like a unique tool with a very specific purpose. That is until I came across the dreaded Bogo sort.

Often called very mean names such as Stupid sort, Bobo sort, Monkey sort, you tend to get a clear impression that these are counted among the most popular of algorithms by Computer Science Majors. Rightly so, it has a big O notation runtime of O(n!). That’s pretty slow and not really helpful, so why even mention it ? It doesn’t seem to be a tool you’d wanna use right ? Let’s take a closer peek.

class Array
   def sorted?
     for x in 1 ... self.length
      return false if self[x-1] > self[x]
     end
  return true
 end
  def bogosort
   self.shuffle! until self.sorted?
    return self
  end
 end
#This is what Bogo sort looks like in Ruby ! 

Under the hood: It’s an awkward card shuffle

Notice the other runtimes on this chart, way faster then Bogo Sort.

So how does it work? well, Bogo sort simply shuffles a collection randomly until it is sorted. A little silly right ? why does this even exist. Let’s have a little thought experiment. Imagine you want to sort out a deck of cards like this algorithm. You would have to do the following…

1. Take a deck of cards out of a pack
2. Throw them up into the air
3. Pick them all up
4. Check and see if they are in order by suit, color and rank?
5. If not , repeat steps 1, 2, 3, 4

It’s pretty inefficient as far as algorithms go the reason being that the chance that any given shuffle of a set of objects will end up in , and the worst case is infinite since there’s no guarantee that a random shuffling will ever produce a sorted sequence.

Oddly enough the best case runtime is O(n) since a single pass through the elements may suffice to order them. This would be rare though, which again isn’t very helpful. Yet it’s still pretty interesting. maybe there is something more to this tool.

Quantum Bogosort !

Turns out Quantum computing has found a use for our seemingly useless algorithm. In the context of the sub-atomic and quantum levels the reality is much different. Ideas such as the binary bit are replaced with the qubit. This allows us as passionate technology enthusiasts to reconsider our approach towards everything including problem solving with traditional algorithms.

Using the mini worlds interpretation of quantum mechanics, the concept of Bogo sort, and the Scheme programming language, Jason Orendorff managed to create something interesting and useful. It’s a little complex but very interesting, please click on the link below.

Check out Quantum Bogo Sort with Jason Orendorff:

When we begin to blend other fields into computer science, new and exciting possibilities rise to the surface. Which may just give over looked algorithms like Bogo sort a chance to truly shine. So think twice about picking on ol’ Bogo sort, it may just be a helpful tool in the near future.

Check out this link for a visual on how Bogo sort works. I’d bring a snack, it’s gonna take a while…

More Links:

https://www.geeksforgeeks.org/bogosort-permutation-sort/#:~:text=For%20example%2C%20if%20bogosort%20is,until%20the%20deck%20is%20sorted.