Reversal algorithm for array rotation
Let AB are the two parts of the input array where A = arr[0..d-1] and B = arr[d..n-1].
The idea of the algorithm is:
- Reverse A to get ArB. / Ar is reverse of A /
- Reverse B to get ArBr. / Br is reverse of B /
- Reverse all to get (ArBr) r = BA.
void Array::reverse(int *arr, int start, int end) {
int size = end - start;
for (int i=0; i<size/2; i++) {
swap(arr[start+i], arr[end-i]);
}
}
// Rotate array to left
void Array::reverseRotate(int *arr, int size, int n) {
n = n % size;
reverse(arr, 0, n-1);
reverse(arr, n, size-1);
reverse(arr, 0, size-1);
for (int i=0; i<size; i++) {
cout << arr[i] << endl;
}
}