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[10] = {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
Posted by
Labels: ,