7
$\begingroup$

We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for d = 2, the resultant rotated array is {3, 4, 5, 6, 7, 1, 2}.

One algorithm which does this goes as follows:

  1. Reverse A[0..d-1] (0-indexing)
  2. Reverse A[d..n-1]
  3. Reverse A[0..n-1]

These three steps surprisingly rotate the array correctly. What is the math behind this algorithm? Why does it give a correct solution? It feels magical to me. I am not able to put up a formal proof of its correctness.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Here is a proof by picture, which follows the steps of the algorithm: $$ 0,\ldots,d-1,d,\ldots,n-1 \\ d-1,\ldots,0,d,\ldots,n-1 \\ d-1,\ldots,0,n-1,\ldots,d \\ d,\ldots,n-1,0,\ldots,d-1 $$ You can easily turn this into a formal proof by giving a formula for the permutation after each step, which you can easily prove correct.

$\endgroup$
2
  • $\begingroup$ This is a good starting point but not sure how to give formula for the permutation? $\endgroup$ Aug 12, 2018 at 14:04
  • $\begingroup$ Take it as an exercise. Your formula could involve two separate cases. $\endgroup$ Aug 12, 2018 at 16:52
1
$\begingroup$

First, we can see the rotation problem (as described in the question) as equivalent to: interchange of two blocks of elements which are at index-ranges $[0, d-1]$ and $[d, n-1]$. Let's call these blocks, with elements exactly as the original array $A$, as $B_1$ and $B_2$. As result of this interchange, the order of these blocks in $A$ should change from $(B_1,B_2)$ to $(B_2,B_1)$.

In the provided algorithm, after the first two steps, array $A$ would contain:

$B_1$(reversed), followed by, $B_2$(reversed).

Now, if this modified array $A$ is read/iterated from end to start, it should return elements in order:

$[B_2$(reversed)(reversed) $\leftrightarrow B_2]$, followed by, $[B_1$(reversed)(reversed) $\leftrightarrow B_1]$.

which is the intended order. The third step modifies $A$ to reflect such order, by reversing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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