Block swap algorithms

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

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
  1. D. Gries, H. Mills (1981), Swapping Sections
  2. Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.