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 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.

Ancestors (12)

  1. c
  2. 4
  3. Imperative programming
  4. 2016
  5. Past exam of the year 1 of the computer science course of the University of Oxford
  6. Year 1 of the computer science course of the University of Oxford
  7. Computer science course of the University of Oxford
  8. Undergraduate course of the University of Oxford
  9. Course of the University of Oxford
  10. University of Oxford
  11. List of universities
  12. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version