The devil

Computer Science Level 5

Bogosort, also known as stupid sort or monkey sort, is a rather (in)famous sorting technique known for its inefficiency. In bogosort, you shuffle the array randomly and check if it's sorted; if it isn't, you repeat the whole thing.

Since you're clever, you come up with a better version of bogosort. If some of the first and last few values (a prefix and a suffix of the array) are already correctly sorted, we don't need to include them in the shuffle; we can fix them in place. For example, suppose that we shuffle and get \((1,2,6,4,5,3,7)\); we can now fix the \(1,2,7\) and only shuffle \(6,4,5,3\). Note that although \(4,5\) are in the correct place, we still include them in the shuffle since they are not "first and last few values".

Let \(X(n)\) be the expected number of shuffles needed to sort the first \(n\) natural numbers, given that none of the numbers are in the right place initially (so all numbers are included in the shuffle). If \(X(15)\) can be written as \(\frac{A}{B}\) where \(A\) and \(B\) are coprime positive integers, what is the value of \(A+B\)?

Bonus Question What is the expected running time of the modified bogosort?

Not an original problem

Problem Loading...

Note Loading...

Set Loading...