Rotate an array by K Position left.

We have to rotate an a sorted Array by k points. For example, if k=3, for the below array
A ={2, 4, 7, 9, 10, 12, 28, 30, 34, 50}
then after rotation the final array will be A ={9, 10, 12, 28, 30, 34, 50, 2, 4, 7}.

Solution:
 Method 1: Brute Force method : Rotate by one position at a time

/** Rotate the Array k places by rotating by one position at a time
 */
void rotate(int *arr, int n, int k){
    for (int cnt = 0; cnt < k; cnt++){
        int temp = arr[0];
        int i=0;
        for (; i < n-1; i++)
            arr[i] = arr[i+1];
        arr[i] = temp;
    }
}

Method 1: Swapping & Reversing the Sub-array method: 

For i= 0 to k-1
swap a[i], a[n-i-1]
// arr: 50, 34, 20,
9, 10, 12, 18, 7, 4, 2

Reverse elements from k to n-k-1.        // arr: 50, 34, 20, 18, 12, 10, 9, 7, 4, 2

Reverse elements from 0 to n-k-1.       // arr: 9, 10, 12, 18, 20, 34, 50, 7, 4, 2
Reverse elements from n-k to n-1.       // arr: 9, 10, 12, 18, 20, 34, 50, 2, 4, 7

/**
 * Function to rotate the array arr of size n by k positions
 * We will examine the state of array after each step for following input values
 * arr: 2, 4, 7, 9, 10, 12, 18, 20, 34, 50
 *   n: 10
 *   k: 3
 *
 * Expected Output: 9, 10, 12, 18, 20, 34, 50, 2, 4, 7
 */
void rotate(int *arr, int n, int k){
 for(int i=0; i < k; i++)
        swap(arr,i,n-i-1);
    // arr: 50, 34, 20, 9, 10, 12, 18, 7, 4, 2
    reverse(arr,k,n-k-1);
    // arr: 50, 34, 20, 18, 12, 10, 9, 7, 4, 2
    reverse(arr,0,n-k-1);
    // arr: 9, 10, 12, 18, 20, 34, 50, 7, 4, 2
    reverse(arr,n-k, n-1);
    // arr: 9, 10, 12, 18, 20, 34, 50, 2, 4, 7
}

/**
 * Swap two elements at position a & b of Array arr.
 */
void swap(int *arr, int a, int b){
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
}

/**
 * Reverse all the elements of array arr between positions a & b (both inclusive)
 */
void reverse(int *arr, int a, int b){
    for(int i=0; i<=(b-a)/2; i++)
        swap(arr, a+i, b-i);
}

/**
 * Function to print the array
 */
void printArray(int arr[], int size){
    for(int i = 0; i < size; i++)
        cout<<arr[i]<<" ";
}

Method-4: Using an Auxiliary Array

If we use a separate array to store the result then things becomes easy. I am sure you can write the function for this one :)

void rotateUsingExtaArray(int arr[], int n, int k){
    for(int i=0; i < n; i++)
        b[i] = arr[(i+k)%n];
}

Time complexity: O(n).   Space Complexity: O(n)

Method-6: Juggling Algorithm
In this method, the array is divided into M sets, where M = GCD(n, k), and rotate the corresponding elements in each set: For Example: If we want to rotate the below array by 2 points

1 2 3 4 5 6

M = GCD(6, 2) = 2;

First Set Moves:

3 2  5 4  1 6

Second Set Moves:

3 4 5 6 1 2

/**
 * Rotate the array arr of size n by k places
 */
void rotateJuggling(int *arr, int n, int k){

    int i, j, p, temp;
    for (i = 0; i < gcd(k, n); i++){

        // moving i'th
        temp = arr[i];
        j = i;
        while(1){

            p = j + k;
            if (p >= n)
                p = p - n;
            if (p == i)
                break;
            arr[j] = arr[p];
            j = p;
        }
        arr[j] = temp;
    }
}

Time complexity:     O(n).
Space Complexity:   O(1).