Rotate an Array 'k' times
Rotation of an array is either
left shifting or right shifting the elements of an array. Rotation in an array
is performed by overwriting one element with another. To perform rotation 'k' times,
we actually shift the elements of an array 'k' times in a specified direction.
A left rotation of an array shift the array elements to left by
one position whereas a right rotation shift the array elements to the right by
one postilion.
Suppose, an array arr[]={1,2,3,4,5}, A left rotation on arr will result in arr[]={2,3,4,5,1}, whereas a right
rotation will result in arr[]={5,1,2,3,4}
'k' rotations on an array will shift the elements 'k' times. Suppose k=3 left rotations are performed on arr[]={1,2,3,4,5}then
the rotations will be performed as:
arr[]={1,2,3,4,5} -> {2,3,4,5,1} -> {3,4,5,1,2} ->
{4,5,1,2,3}
Similarly, k=3 right rotations on the arr[]={1,2,3,4,5} will result in
arr[]={1,2,3,4,5} -> {5,1,2,3,4} -> {4,5,1,2,3} ->
{3,4,5,1,2}
Source Code
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 | #include <stdio.h> #define SIZE 10000 //Macro to define maximum Array size void leftrotation(int arr[], int n, int k) //Function to perform Left rotation { int i, j; int temp[k]; //Temporary array for (i = 0; i < k; i++) { temp[i] = arr[i]; } for (i = 0; i < n - k; i++) { arr[i] = arr[i + k]; } for (i = n - k; i < n; i++) { arr[i] = temp[i - (n - k)]; } } void rightrotation(int arr[], int n, int k) //Function to perfrom Right rotation { int i, j; int temp[k]; for (i = n - k; i < n; i++) { temp[i - (n - k)] = arr[i]; } for (i = n - 1; i >= k; i--) { arr[i] = arr[i - k]; } for (i = 0; i < k; i++) { arr[i] = temp[i]; } } void display(int arr[], int n) //Display Array Elements { int i; for (i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); } int main(int argc, char const *argv[]) { int arr[SIZE]; int i, n, k; char ch; printf("Enter SIZE of array : "); scanf("%d", &n); printf("Enter Array elements\n"); for (i = 0; i < n; i++) { scanf("%d", &arr[i]); } printf("Enter Rotation Value 'k': \n"); scanf("%d", &k); printf("Enter Direction of Rotation (Left/Right : l/r) : "); scanf("%c", &ch); scanf("%c", &ch); switch (ch) { case 'l': case 'L': printf("Before Rotation : "); display(arr, n); leftrotation(arr, n, k); printf("After '%d' Left Rotation : ", k); display(arr, n); break; case 'r': case 'R': printf("Before Rotation : "); display(arr, n); rightrotation(arr, n, k); printf("After '%d' Right Rotation : ", k); display(arr, n); break; default: printf("Wrong Choice\n"); } } |
Output
Enter SIZE of array : 5
Enter Array elements
1 2 3 4 5
Enter Rotation Value 'k':
3
Enter Direction of Rotation (Left/Right : l/r) : r
Before Rotation : 1 2 3 4 5
After '3' Right Rotation : 3 4 5 1 2
Enter SIZE of array : 5
Enter Array elements
10 20 30 40 50
Enter Rotation Value 'k':
2
Enter Direction of Rotation (Left/Right : l/r) : l
Before Rotation : 10 20 30 40 50
After '2' Left Rotation : 30 40 50 10 20
Complexity : O(n)
0 comments:
Post a Comment