array rotation Algorithm
Array rotation is a popular algorithmic technique used in computer programming to modify the positions of elements in an array. The main idea behind the algorithm is to rotate the elements of an array by a specified number of positions, either to the left or right, such that the elements are shifted to their new positions, with the elements at the ends "wrapping around" to the beginning or end of the array. This operation can be performed in various ways, including using temporary arrays, swapping elements, or by reversing segments of the array.
One common method for implementing array rotation is called the Juggling Algorithm. This approach divides the array into sets or blocks, where each block consists of elements that get moved to the same position after rotation. The algorithm rotates the elements within each block and then moves on to the next block until all elements are rotated. This method minimizes the number of memory accesses and is more efficient than other approaches, especially when the array size and rotation count share a common divisor. The time complexity of the Juggling Algorithm is O(n), where n is the size of the array, making it an efficient solution for large-scale applications.
#include <iostream>
#include <cassert>
void swap( int & a, int & b)
{
int temp = a;
a = b;
b = temp;
}
/**
* reverse an array from index 'start' to index 'end'
* @param arr [The array]
* @param start [The start index]
* @param end [The end index]
*/
void reverse( int * arr, int start, int end )
{
while( start < end ) {
swap(arr[start], arr[end]);
++start;
--end;
}
}
/**
* [leftRotate - rotate an array of length n with r rotations in left direction
* @param arr - the array
* @param n - size of array
* @param r - n number of rotations
*/
void leftRotate( int* arr, int n, int r )
{
r = r % n;
reverse( arr, 0, r-1);
reverse( arr, r, n-1);
reverse( arr, 0, n-1);
}
/**
* [rightRotate - rotate an array of length n with r rotations in left direction
* @param arr - the array
* @param n - size of array
* @param r - n number of rotations
*/
void rightRotate( int* arr, int n, int r )
{
r = r % n;
reverse( arr, 0, n-1);
reverse( arr, 0, r-1);
reverse( arr, r, n-1);
}
int main()
{
int n, r, d;
std::cout << "Enter size of array :";
std::cin >> n;
std::cout << "Enter the contents of array:";
int * arr = new int[n];
for ( int i = 0; i < n; ++i ) {
std::cin >> arr[i];
}
std::cout << "Enter number of rotations you need:";
std::cin >> r;
std::cout << "Direction (left = 0, right = 1):";
std::cin >> d;
assert((d == 0) || (d == 1));
if ( d == 0 ) {
leftRotate(arr, n, r);
} else {
rightRotate(arr, n, r);
}
std::cout << "The array after rotation:\n";
for ( int i = 0; i < n; ++i ) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
return 0;
}
