C Program for Block Swapping Algorithm

Program for Block Swapping Algorithm in C

Today we will learn about how to make Program for Block Swapping Algorithm in C programming language.

Now , let’s understand it with an example A[5] = {1, 2, 3, 4, 5}

 after block swapping array will be A[5] =  {5, 4, 1, 2, 3}.

On rotation, we will shift the one element to the last position and shift the next elements to one position.

Block Swapping Algorithm
Block Swapping Algorithm

Algorithm :

 

  • Initialize the array arr[ ] and then split them into two array A and B.
  • A[ ] = arr[0…p-1] and B[ ] = arr[p….size-1] , p denotes the number of rotations.
  • Repeats until size of array A = size of array B.
  • If A[ ] is shorter, Divide array B into two array say BL[ ] and BR[ ], in which size of BL array is same as size of array A[ ] . Here BL[ ] = left part of B[ ] and BR[ ] = right part of B[ ].
  • Swap  A[ ] with BR[ ], Now A[ ] is at its final place.
  • Recur on B[ ].
  • If A[ ] is longer then,
  • Divide A[ ] into two arrays AL[ ] and AR[ ].
  • Swap  B[ ] with AL[ ], Now B[ ] is at its final place.
  • Recur on A[ ].

C  Program based on above algorithm:

#include<stdio.h>
using namespace std;

/*Prototype for swap functions */
void swap (int arr[], int fi, int si, int d);

void
Rotate (int arr[], int p, int n)
{
/* Return If number of elements to be rotated
is zero or equal to array size */
if (p == 0 || p == n)
return;

/*If number of elements to be rotated
is exactly half of array size */
if (n - p == p)
{
swap (arr, 0, n - p, p);
return;
}

/* If A is shorter */
if (p < n - p)
{
swap (arr, 0, n - p, p);
Rotate (arr, p, n - p);
}
else /* If B is shorter */
{
swap (arr, 0, p, n - p);
Rotate (arr + n - p, 2 * p - n, p);
}
}

/*This function swaps d elements starting at index fi
with p elements starting at index si */
void
swap (int arr[], int fi, int si, int p)
{
int i, temp;
for (i = 0; i < p; i++)
{
temp = arr[fi + i];
arr[fi + i] = arr[si + i];
arr[si + i] = temp;
}
}

// Driver Code
int
main ()
{
int arr[100],n,p;
printf ("number of rotation = ");
scanf ("%d", &p);
printf ("Size of array = ");
scanf ("%d", &n);
printf ("element of array = ");
for (int i = 0; i < n; i++)
{
scanf ("%d", &arr[i]);
}
Rotate (arr, p, n);

for (int i = 0; i < 8; i++)
printf ("%d", arr[i]);

return 0;
}

Output :

number of rotation = 2
Size of array = 5
element of array = 1
2
3
4
5
34512