Assume every indicated segment lies within array bounds, and lengths are nonnegative. Use a temporary value of element type 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;
The first procedure even works for . For the second, disjointness ensures that each swap exchanges the two original entries at offset 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.

Ancestors (12)

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