# Program to Rotate Array Using Block Swap Algorithm

• Write a program to rotate an array using block swap algorithm.
• Array rotation Block swap algorithm implementation.

Given an integer array of size N we have to rotate it by K elements without using any extra memory space.
For Example :

```Input Array : 1 2 3 4 5 6 7 8
K = 3
Output : 4 5 6 7 8 1 2 3
```

Let inputArray be an integer array of size N.

Array Rotation Block Swap Algorithm
• Split inputArray into two sub Array X and Y, where X is from index 0 to K-1 and Y is from index K to N-1.
• If X is smaller than Y
• Split Y into YLeft and YRight such that size of YRight is equal to size of X. inputArray will be X|YLeft|YRight.
• Swap X and YRIght. Now, inputArray will look like YRight|Yleft|X. X is now in correct position.
• Recursively block swap YRight and YLeft.
• If Y is smaller than X
• Split X into XLeft and XRight such that size of XLeft is equal to size of Y. inputArray will be XLeft|XRight|Y.
• Swap Y and XLeft. Now, inputArray will look like Y|XRight|XLeft. Y is now in correct position.
• Recursively block swap XRight and XLeft.
• If size of X is equal to size of Y, then swap X and Y.
Time Complexity : O(n)

## C program to rotate an array using block swap algorithm.

```#include <stdio.h>

/* This function swaps two sub arrays of length L,
starting from left and right index */
void swapArraySegment(int *array, int left, int right, int L){
int i, temp;
for(i = 0; i < L; i++) {
/* swapping array element at index left+i and right+i */
temp = array[left + i];
array[left + i] = array[right + i];
array[right + i] = temp;
}
}

void rotateArray(int *array, int N, int size) {
/* Input Validation */
if(array == NULL || size == 0 || N == 0 || N == size)
return;

/* If elements to be rotated is equal to
first half of the given array  */
if(size - N == N){
/* swap left and right half of array */
swapArraySegment(array, 0, size-N, N);
return;
}

/* If X(left Segment) is smaller than Y */
if(N < size-N) {
/* Swap X and Y_right */
swapArraySegment(array, 0, size-N, N);
/* Recursively swap remaining elements */
rotateArray(array, N, size-N);
} else {
/* If Y(right Segment) is smaller than X */
swapArraySegment(array, 0, N, size-N);
rotateArray(array+size-N, 2*N-size, N);
}
}

int main(){
int array = {0,1,2,3,4,5,6,7,8,9};
int i;

printf("Original Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}
rotateArray(array, 4, 10);

printf("\nRotated Array\n");
for(i = 0; i<10; i++){
printf("%d ", array[i]);
}

return 0;
}
```
Output
```Original Array
0 1 2 3 4 5 6 7 8 9
Rotated Array
4 5 6 7 8 9 0 1 2 3
```