1
$\begingroup$

Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let $\mathrm{Reverse}(A, i, j)$ be a procedure that reverses the subarray $A[i], A[i + 1], \dots , A[j]$ of the array $A$ while leaving the remaining elements of the array unaffected. Prove that the following algorithm sorts the array $A$ and also terminates.

for i := 1 to n − 1
  while A[i] ≠ i do
    Reverse(A, i, A[i])

I am able to prove this if the elements are in descending order. Why does this algorithm work for an arbitrary order?

$\endgroup$
3
$\begingroup$

If the algorithm terminates at all then $A[i] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i_0$, we know that $A[j] = j$ for $j < i_0$, and so $A[i_0],\ldots,A[n]$ is a permutation of $i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices to show that the inner while loop terminates when $i = 1$.

Suppose that the inner while loop never terminates when $i = 1$. Let $j$ be the maximal value which appears infinitely many times as $A[1]$. After finitely many iterations, $A[1] \leq j$ always. Since $A[1] = j$ infinitely many times, there must be some subsequent iteration in which $A[1] = j$. After that iteration, $A[j] = j$. In all subsequent iterations, $A[1] \leq j$, which ensures that $A[j]$ stays $j$, guaranteeing that $A[1]$ never equals $j$ again. However, this contradicts the definition of $j$.

The maximal number of iterations of the inner loop is A000375. There is no known formula!

I couldn't find the sequence for the maximal total number of iterations of the inner loop (over all $i$) on OEIS.

$\endgroup$
5
  • $\begingroup$ Its a good answer, but I think you will need to explain more why $j$ will stay at its place. We can prove (by induction on the time $t$ after we saw $j$ for the first time) that for any $A[1]=k$ which came after the iteration for which $A[1]=j$, we have $k<j$ (and not only $k\le j$). This is followed by that $j$ is maximal and is unique (there is only one $j$ in the array). $\endgroup$ – nir shahar May 4 at 20:39
  • $\begingroup$ It's a simple induction. $\endgroup$ – Yuval Filmus May 4 at 20:40
  • $\begingroup$ Can u please explain it with an example like taking a small array e.g [9,3,1,8]?? $\endgroup$ – Danjing_Chaw May 5 at 11:36
  • $\begingroup$ Your example is not a permutation of $1,\ldots,n$. Also, you can work out any specific example by hand, or by programming the algorithm. $\endgroup$ – Yuval Filmus May 5 at 12:02
  • $\begingroup$ Okay got it!. It is clear now. $\endgroup$ – Danjing_Chaw May 5 at 14:42
1
$\begingroup$

If you're familiar with cycle sort, you can start to see that this algorithm also operates in a similar way (although it's super inefficient).

Essentially, the inner loop doesn't terminate until the element in the current position $i$ is $i$. So when the outer loop moves on to the next element, you are guaranteed that the subarray to the left is sorted and in the final state ($1,2,3,\dots,i-1$)

Now to prove that the inner loop terminates... assume that it never terminates. So at a certain point, the value at $A[i]$ will loop through some values $t_1,t_2,\dots,t_k$, none of which are $i$. Let $T=\{\text{all values $A[i]$ loops through infinitely}\}$. Clearly $|T|<n-i$.

When $t_2$ is at $i$, then $t_1$ will be at position $t_1$. For $t_1$ to ever return to position $i$ (which it must as it's an infinite loop), there must be a $t_p>t_1$ in $T$. Otherwise $A[t_1]$ will never be affected by a reversal.

By symmetry this is true of all $t_j \in T$. Hence $T$ must contain an element which is strictly larger than every element in $T$... a contradiction. Hence the inner loop terminates.

You could also say that this finite set $T$ must contain an infinite sequence of strictly increasing numbers, which is not possible.

$\endgroup$
1
  • $\begingroup$ @Yuval Filmus Thanks for the edits $\endgroup$ – Hannah W. May 5 at 10:08

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.