2
$\begingroup$

This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort.

Assume that $A$ is an array initialized by a random permutation on the set $I_n=\{1,2,\ldots, n\}$.

Consider the next algorithm:

While $A$ is not sorted:

  • Pick two random numbers $i\leq j\in\{1,2,\ldots, n\}$ uniformly and reverse $A[i\ldots j]$.

For example, if the initial array was $A=1,4,2,3,5,6$ and the algorithm picks $i=2,j=5$ then the value of $A$ after the reversal would be $1,5,3,2,4,6$.

Notice that this algorithm halts after finite number of iterations with probability 1.

What is the expected number of iterations for the algorithm?

$\endgroup$
  • 2
    $\begingroup$ What have you tried and where did you get stuck? This is related to pancake sorting which has been studied extensively. A similar question has been asked before, but there's no concrete answer. $\endgroup$ – Raphael Mar 1 '15 at 13:19
  • $\begingroup$ @Raphael - I'm familiar with the pancake sorting problem, but is not the same. In pancake sorting you are only allowed to flip a prefix of the array. Also, in my question I don't ask about the minimum number of flips needed, but rather the expected number of flips when the interval is picked at random. It's quite easy to show that this ends with probability 1 (the markov chain whose states are the symmetric group $S_n$ who represent the current state of the algorithm is finite and connected), but this offers no help in computing the expected number of reversals. $\endgroup$ – R B Mar 1 '15 at 14:55
  • $\begingroup$ @Raphael - The linked question does indeed discusses general flips, and not only prefix reversals, but once again seeks the optimal number of flips. $\endgroup$ – R B Mar 1 '15 at 14:56
  • $\begingroup$ Again, what have you tried and where did you get stuck? We expect you to make a serious effort before asking and show us what you progress you've made. This helps us avoid duplicating effort and often helps clarify your thought process and what kind of an answer you are looking for. If it's a question you care about, you should already be thinking hard about it before you ask, so you should be able to tell us something about your efforts so far. $\endgroup$ – D.W. Mar 1 '15 at 19:19
2
$\begingroup$

$\Omega(n!)$ is an easy lower bound: your algorithm certainly needs at least $\Omega(n!)$ iterations on average. Obviously, you need to try at least $\Theta(n!)$ different permutations of the array before you have a decent chance of getting the elements into sorted order (since you started with a uniformly random permutation).

Also, one can show that $O(n! \cdot n \lg n)$ is an upper bound on the number of iterations needed. Here's why. It's known that there is a constant $c$ such that composing $k=c n \lg n + o(n \lg n)$ randomly chosen transpositions gives you something that is close to a random permutation. So, look only at every $k$th iteration of your algorithm, and consider the permutation generated at each such time instant. Each one is approximately a random permutation (independent of all others). After checking $\Theta(n!)$ independent random permutations, with good probability at least one of them will put the array into sorted order. Therefore, your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations. Or, to put it another way, if we tested for sortedness only at every $k$th iteration of your algorithm, the result would be essentially equivalent to Bogosort, so your algorithm performs at most $k$ times as many iterations as Bogosort -- thus your algorithm needs at most $O(n! \cdot k) = O(n! \cdot n \lg n)$ iterations.

So we know that the answer is at least $\Omega(n!)$ and at most $O(n! \cdot n \lg n)$. Those two answers are very close (they differ only by a factor that is logarithmic in the number of iterations), so this doesn't leave much of a gap -- it almost totally resolves the question. If you wanted a more precise answer, probably a more delicate analysis would be needed to eliminate the gap -- but lacking clear motivation for studying this problem, it's not clear it's worthwhile to spend that level of energy on it.


How do we know that composing $O(n \lg n)$ random transpositions gives you something close to a random permutation? That was proven in the following paper:

Generating a Random Permutation with Random Transpositions. Persi Diaconis, Mehrdad Shahshahani. 1981.

See also https://paulrs.wordpress.com/2014/07/22/generating-a-random-permutation/.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.