1.1.2 Array Rotation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

/*

These functions are equivalent to `std::rotate()`, taking three iterators `lo`, `mid`, and `hi`
(`lo` $\leq$ `mid` $\leq$ `hi`) to perform a left rotation on the range [`lo`, `hi`). After the
function call, [`lo`, `hi`) will consist of the concatenation of elements originally in
[`mid`, `hi`) + [`lo`, `mid`). That is, the range [`lo`, `hi`) will be rearranged in such a way that
the element at `mid` becomes the first element of the new range, and the element before `mid`
becomes the last element, all while preserving the relative ordering of elements within the two
rotated subarrays.

All three versions below achieve the same result using in-place algorithms.

- `rotate1(lo, mid, hi)` uses a straightforward swapping algorithm requiring ForwardIterators.
- `rotate2(lo, mid, hi)` requires BidirectionalIterators, employing a well-known trick with three
  simple inversions.
- `rotate3(lo, mid, hi)` requires random-access iterators, applying a juggling algorithm which first
  divides the range into `gcd(hi - lo, mid - lo)` sets and then rotates the corresponding elements
  in each set.

Time Complexity:
- O(n) per call to all versions, where $n$ is the distance between `lo` and `hi`.

Space Complexity:
- O(1) auxiliary for all versions

*/

#include <algorithm>
#include <numeric>

template<class It>
void rotate1(It lo, It mid, It hi) {
  if (lo == mid || mid == hi) {
    return;
  }
  It next = mid;
  while (lo != next) {
    std::iter_swap(lo++, next++);
    if (next == hi) {
      next = mid;
    } else if (lo == mid) {
      mid = next;
    }
  }
}

template<class It>
void rotate2(It lo, It mid, It hi) {
  if (lo == mid || mid == hi) {
    return;
  }
  std::reverse(lo, mid);
  std::reverse(mid, hi);
  std::reverse(lo, hi);
}

template<class It>
void rotate3(It lo, It mid, It hi) {
  if (lo == mid || mid == hi) {
    return;
  }
  int n = hi - lo, jump = mid - lo;
  int g = std::gcd(jump, n), cycle = n / g;
  for (int i = 0; i < g; i++) {
    int curr = i, next;
    for (int j = 0; j < cycle - 1; j++) {
      next = curr + jump;
      if (next >= n) {
        next -= n;
      }
      std::iter_swap(lo + curr, lo + next);
      curr = next;
    }
  }
}

/*** Example Usage and Output:

before sort:  2 4 2 0 5 10 7 3 7 1
after sort:   0 1 2 2 3 4 5 7 7 10
rotate left:  1 2 2 3 4 5 7 7 10 0
rotate right: 0 1 2 2 3 4 5 7 7 10

***/

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  vector<int> a0, a1, a2, a3;
  for (int i = 0; i < 10000; i++) {
    a0.push_back(i);
  }
  a1 = a2 = a3 = a0;
  int mid = 5678;
  std::rotate(a0.begin(), a0.begin() + mid, a0.end());
  rotate1(a1.begin(), a1.begin() + mid, a1.end());
  rotate2(a2.begin(), a2.begin() + mid, a2.end());
  rotate3(a3.begin(), a3.begin() + mid, a3.end());
  assert(a0 == a1 && a0 == a2 && a0 == a3);

  // Example from: http://en.cppreference.com/w/cpp/algorithm/rotate
  vector<int> a{2, 4, 2, 0, 5, 10, 7, 3, 7, 1};
  cout << "before sort:  ";
  for (const auto &x : a) {
    cout << x << " ";
  }
  cout << endl;

  // Insertion sort.
  for (auto i = a.begin(); i != a.end(); ++i) {
    rotate1(std::upper_bound(a.begin(), i, *i), i, i + 1);
  }
  cout << "after sort:   ";
  for (const auto &x : a) {
    cout << x << " ";
  }
  cout << endl;

  // Simple rotation to the left.
  rotate2(a.begin(), a.begin() + 1, a.end());
  cout << "rotate left:  ";
  for (const auto &x : a) {
    cout << x << " ";
  }
  cout << endl;

  // Simple rotation to the right.
  rotate3(a.rbegin(), a.rbegin() + 1, a.rend());
  cout << "rotate right: ";
  for (const auto &x : a) {
    cout << x << " ";
  }
  cout << endl;
  return 0;
}