patternMinor
Proof of correctness of reversal algorithm for array rotation
Viewed 0 times
arraycorrectnessrotationalgorithmforreversalproof
Problem
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
One algorithm which does this goes as follows:
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.
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:
- Reverse
A[0..d-1](0-indexing)
- Reverse
A[d..n-1]
- 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.
Solution
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.
$$
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.
Context
StackExchange Computer Science Q#96168, answer score: 3
Revisions (0)
No revisions yet.