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]<<" ";
}
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 :)
