Bogosort

There are a myraid of different sorting algorithms: quicksort, merge sort, radix sort, bubble sort, etc. There’s even a whole list of sorting algorithms on Wikipedia. But there’s one sort I like the most…bogosort.

Here’s the pseudocode of Bogosort:

1. Randomly shuffle the array
2. Check if the array is sorted
3. If the array is sorted, return the sorted array. Else, return to step 1.

Here’s an algorithm of Bogosort, written in Ruby and posted in Wikibooks.

class Array
  def bogosort!
    shuffle! until sorted?
  end

  def sorted?
    each_cons(2).all? { |a,b| a <= b }
  end
end

Now, in the worst-case scenario, Bogosort will take an infinite number of random shuffles before successfully sorting the algorithm. But in the best-case scenario, it can take a single shuffle. Even in a normal-case scenario, you can expect it to take a few shuffles before returning the right answer.

Bogosort is interesting to me because it is a nondeterministic algorithm, an algorithm that behaves differently based on the same input. According to Wikipedia:

In computer science, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.

A nondeterministic algorithm can be very powerful, enabling us to approximate good solutions to problems that can’t be solved efficiently by purely deterministic algorithms (i.e, stochastic optimization). For example, nondeterministic algorithms can help deal with NP-complete problems such as the infamous “traveling salesman problem”. Rather than trying out all possible routes and selecting the best one, why not randomly pick a few routes and then check to see which one is the best?

In fact, the very term NP is an abbrevation of the term “nondeterministic polynominal”. Suppose we have a nondeterministic algorithm that is always “lucky” – for example, a bogosort that gets the array sorted after the first shuffle. Obviously, this algorithm would have a polynominal runtime. Hence the name – nondeterministic polynominal.

Of course, in the real world, we can’t just force an algorithm to always be “lucky”. Computer scientists have imagined the idea of a nondeterministic Turing machine that will always get “lucky”, but such machines are impossible to build and are only useful as a thought experiment…as a comparison to our less-lucky deterministic machines.

Using bogosort for an actual sorting problem is a bit silly, as there are already lots of deterministic sorting algorithms that are much more effective. But there are many, many problems where we cannot come up with efficent deterministic algorithms, such as the NP-Complete problems I mentioned. And so we break out the non-deterministic algorithms…and thank bogosort for the inspiration.

For additional information, I would highly recommend reading these two questions on CS.StackExchange: What is meant by “solvable by non deterministic algorithm in polynomial time”? and Bogo sort on NDTM. You may also want to look at this forum topic post on cplusplus.com - P vs NP for alternate ways of explaining the term ‘nondeterministic polynominal’.

And if you want to know of several nondeterministic algorithms that are used to solve real-world problems, please look at the Metaheuristic page on Wikipedia.