How do you rotate an array by d positions?
Short answer: Use the reversal algorithm. To rotate left by d: reverse the first d elements, reverse the rest, then reverse the whole array. It runs in O(n) time with O(1) extra memory. Reduce d with d %= n first.
#include <stddef.h>
static void reverse_range(int *a, size_t lo, size_t hi) /* inclusive */
{
while (lo < hi) {
int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
lo++; hi--;
}
}
void rotate_left(int *a, size_t n, size_t d)
{
if (n == 0) return;
d %= n;
if (d == 0) return;
reverse_range(a, 0, d - 1);
reverse_range(a, d, n - 1);
reverse_range(a, 0, n - 1);
}
/* {1, 2, 3, 4, 5, 6}, d = 2 -> {3, 4, 5, 6, 1, 2} */
Dry run (d = 2):
start 1 2 | 3 4 5 6
reverse [0,1] 2 1 | 3 4 5 6
reverse [2,5] 2 1 | 6 5 4 3
reverse all 3 4 5 6 1 2
Why it works: write the array as A B where A is the first d elements. We want B A. Reversing each part gives Aʳ Bʳ, and reversing the whole thing gives (Aʳ Bʳ)ʳ = B A.
Right rotation by d is left rotation by n - d, or reverse the whole array first and then the two parts.
Other methods
| Method | Time | Extra space |
|---|---|---|
| Rotate by one, d times | O(n·d) | O(1) |
| Copy to a temp array | O(n) | O(n) or O(d) |
| Juggling (GCD cycles) | O(n) | O(1) |
| Reversal | O(n) | O(1) |
Forgetting d %= n is the usual bug: with d = 8 and n = 6, reverse_range(a, 0, 7) writes past the array.
Embedded relevance: the same idea rotates a circular log buffer into chronological order before sending it, without a second buffer.