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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is a good starting point but not sure how to give formula for the permutation? $\endgroup$ Commented Aug 12, 2018 at 14:04
  • $\begingroup$ Take it as an exercise. Your formula could involve two separate cases. $\endgroup$ Commented 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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.