Jump to content

Block swap algorithms

From Wikipedia, the free encyclopedia

In computer algorithms, Block swap algorithms swap two regions of elements of an array. It is simple to swap two non-overlapping regions of an array of equal size. However, it is not simple to swap two non-overlapping regions of an array in-place that are next to each other, but are of unequal sizes (such swapping is equivalent to Array Rotation). Three algorithms are known to accomplish this: Bentley's Juggling (also known as Dolphin Algorithm [1]), Gries-Mills, and Reversal.[2] All three algorithms are linear time O(n), (see Time complexity).

Reversal algorithm

[edit]

The reversal algorithm is the simplest to explain, using rotations. A rotation is an in-place reversal of array elements. This method swaps two elements of an array from outside in within a range. The rotation works for an even or odd number of array elements. The reversal algorithm uses three in-place rotations to accomplish an in-place block swap:

  • Rotate region A
  • Rotate region B
  • Rotate region AB

Gries-Mills and Reversal algorithms perform better than Bentley's Juggling, because of their cache-friendly memory access pattern behavior.

The Reversal algorithm parallelizes well, because rotations can be split into sub-regions, which can be rotated independently of others.

References

[edit]
  1. ^ D. Gries, H. Mills (1981), Swapping Sections
  2. ^ Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.