 Solution

PROCEDURE RotateLeft(k: INTEGER);
VAR r, g, x, y, h, s, j, next: INTEGER; saved: T;
BEGIN
  r := k MOD N;
  IF r # 0 THEN
    x := N; y := r;
    WHILE y # 0 DO h := x MOD y; x := y; y := h END;
    g := x; s := 0;
    WHILE s < g DO
      saved := a[s]; j := s;
      IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END;
      WHILE next # s DO
        a[j] := a[next]; j := next;
        IF j >= N-r THEN next := j-(N-r) ELSE next := j+r END
      END;
      a[j] := saved; s := s+1
    END
  END
END RotateLeft;

The conditional calculation of next implements addition modulo

N

without first forming a possibly overflowing j+r. Oberon's MOD with positive divisor supplies the nonnegative remainder. The first loop is the Euclidean algorithm, with loop invariant

g cd (x, y) = g cd (N, r)

and decreasing nonzero remainder.

For the outer loop, cycles with representatives below s are complete and every other cycle retains its original values. In one cycle, write

c_{t} = (s + t r) mod N

. The inner loop invariant is saved = A[s],

j = c_{t}

, and

a [c_{u}] = A [c_{u + 1}]

for

0 \leq u < t

, with the remaining sources still untouched. When the next index returns to s, the saved value closes the cycle. The cycle length is

N / g

: writing

N = g N^{'}

and

r = g r^{'}

with

g cd (N^{'}, r^{'}) = 1

, the least positive

t

with

t r \equiv 0 (mod N)

N^{'}

. Each residue class modulo

g

is one cycle, justifying the chosen representatives.

Every element is read once and written once: $2 N$ element accesses, compared with

2 N k

for

k > 1

repetitions of part (b). The zero rotation uses none. The running time is

O (N)

and auxiliary space is constant; the original array

A

is proof notation, not a copy made by the program.

 Read the full article

 New to topics? Read the docs here!