Write the segment as , where and . The desired array rotation is . Reverse each block, then the whole segment:The state changes are , using the list reversal identity supplied in the paper and reversal being an involution. Three reversals implement the right rotation in time and auxiliary space. The initial return covers empty and identity rotations.
PROCEDURE rotate(i, n, k: INTEGER);
BEGIN
IF (k = 0) OR (k = n) THEN RETURN END;
reverse(i, n-k);
reverse(i+n-k, k);
reverse(i, n)
END rotate;Let and be the lengths of the left and right blocks. Exchange the smaller block with the equally long block at the opposite end.If , split with . The first block swap sends to ; is now in its final suffix. Rotate the remaining prefix of length right by to send to . If , split with . The swap sends to ; the fixed prefix is , and rotating the remaining length- suffix right by restores . In both cases the exchanged segments are disjoint.
PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
IF (k = 0) OR (k = n) THEN RETURN END;
a := n-k; b := k;
IF a = b THEN
blockswap(i, i+a, a)
ELSIF a < b THEN
blockswap(i, i+b, a);
rotate(i, b, b-a)
ELSE
blockswap(i, i+a, b);
rotate(i+b, a, b)
END
END rotate;The remaining length strictly decreases, so induction on proves algorithm termination and correctness. This implements the block-exchange rotation. It uses only simple explicit variables, but its recursive call stack can have depth when one block has length ; the iterative version removes that extra storage.
Replace the sole recursive call by updates to the current segment's parameters:The loop invariant is that every position outside the current unresolved segment already has its final value, while rotating the current segment by the current
PROCEDURE rotate(i, n, k: INTEGER);
VAR a, b: INTEGER;
BEGIN
WHILE (k > 0) AND (k < n) DO
a := n-k; b := k;
IF a = b THEN
blockswap(i, i+a, a);
RETURN
ELSIF a < b THEN
blockswap(i, i+b, a);
n := b; k := b-a
ELSE
blockswap(i, i+a, b);
i := i+b; n := a; k := b
END
END
END rotate;k completes the original array rotation. The block decompositions in part (ii) prove preservation. The positive unresolved length decreases in each continuing branch; the equal-block branch finishes immediately. The same rotation now uses auxiliary space, including control storage, and leaves the rest of the array untouched.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.For one pass, after the shifts at offsets greater than
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;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 times therefore gives the required array rotation. The method uses one extra T variable and time, with auxiliary space. The early return avoids all accesses for an identity rotation. Articles by others on the same topic
There are currently no matching articles.