Block swap algorithms: Difference between revisions
Wl |
|||
| Line 1: | Line 1: | ||
{{Context|date=July 2019}} |
{{Context|date=July 2019}} |
||
'''Block swap algorithms''' |
'''Block swap algorithms''' swap two elements of an [[Array data structure|array]] in computer [[algorithm]]s. 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. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.<ref>Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.</ref> All three algorithms are linear time [[Big O notation| |
||
O(n)]], (see [[Time complexity]]). |
O(n)]], (see [[Time complexity]]). |
||
Revision as of 11:34, 5 August 2020
 | This article provides insufficient context for those unfamiliar with the subject. (July 2019) |
Block swap algorithms swap two elements of an array in computer algorithms. 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. Three algorithms are known to accomplish this: Bentley's Juggling, Gries-Mills, and Reversal.[1] 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 number of elements or an 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
- ^ Jon Bentley, "Programming Pearls", pp. 13–15, 209-211.
 | This article needs additional or more specific categories. (July 2019) |