= Solution
Save the last entry, shift the others right in descending index order, and put the saved value at the left. Descending order prevents overwriting an unread entry.
``
PROCEDURE rotate(i, n, k: INTEGER);
VAR x: T; step, t: INTEGER;
BEGIN
IF (k = 0) OR (k = n) THEN RETURN END;
step := 0;
WHILE step < k DO
x := m[i+n-1];
t := n-1;
WHILE t > 0 DO
m[i+t] := m[i+t-1];
t := t-1
END;
m[i] := x;
step := step+1
END
END rotate;
``
For one pass, after the shifts at offsets greater than `t`, those positions contain the original preceding entries; offsets through `t` are still available, and `x` retains the original last entry. The <loop variant> `t` decreases to zero. The outer <loop invariant> is that the segment has been rotated right by `step` places relative to its initial state. Repeating a one-step <cyclic permutation> $k$ times therefore gives the required <array rotation>. \b[The method uses one extra `T` variable and $O(kn)$ time], with $O(1)$ auxiliary space. The early return avoids all accesses for an identity rotation.
Back to article page
