Assume every indicated segment lies within array bounds, and lengths are nonnegative. Use a temporary value of element type The first procedure even works for . For the second, disjointness ensures that each swap exchanges the two original entries at offset
T:PROCEDURE swap(i, j: INTEGER);
VAR x: T;
BEGIN
x := m[i]; m[i] := m[j]; m[j] := x
END swap;
PROCEDURE blockswap(i, j, n: INTEGER);
VAR t: INTEGER;
BEGIN
t := 0;
WHILE t < n DO
swap(i+t, j+t);
t := t + 1
END
END blockswap;t without disturbing any other pair. Its loop invariant says that offsets below t have been exchanged, offsets from t through retain their original values, and everything outside the two segments is unchanged. The loop variant proves algorithm termination. A block exchange uses swaps and auxiliary space. The stray wp printed after this source subpart is not an additional requirement.Exchange symmetric pairs, stopping before the middle:Writing for the pre-call array, the loop invariant says that the first and last
PROCEDURE reverse(i, n: INTEGER);
VAR t: INTEGER;
BEGIN
t := 0;
WHILE t < n DIV 2 DO
swap(i+t, i+n-1-t);
t := t + 1
END
END reverse;t positions of the segment already satisfy , all positions between them retain their original values, and positions outside the segment are unchanged. Each swap fixes the next symmetric pair. The loop variant decreases; the two indices are distinct and in bounds whenever the body executes. Exactly swaps reverse the segment, with the odd-length middle element left in place and no accesses for .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.Count element reads and writes, ignoring simple-variable operations. A swap of distinct entries makes two reads and two writes, hence four expensive accesses. For , the three-reversal method therefore costsHere if and are both even, and otherwise.
For either block-exchange version, let , , and let count element swaps. The recurrence is and, when the lengths differ,The Euclidean algorithm preserves under this subtraction. Induction on therefore yieldsThus both block-exchange methods cost accesses, no more than the three-reversal method. Their element-access counts are identical; the iterative one avoids the recursive stack. For example a half-length rotation uses swaps instead of approximately reversal swaps.
Each single-place pass in part (iv) reads every entry once and writes every entry once, costing accesses. For , its accesses beat the block method's for and tie for . For the block method costs strictly less than . All three methods as written return without accesses for or . Repeated shifting can take quadratic time; the reversal and block methods take linear time. These comparisons concern the specified implementations, not a more general cycle-decomposition rotation using several disjoint cycles.
Articles by others on the same topic
There are currently no matching articles.