JavaScript program for block swapping algorithm for array rotation

Rotation of array elements means moving the elements of a given array to the left or right by a specific number of positions. We assume that the array is in the form of a loop and rotate the elements of the edge to the other end. The block-swap algorithm for array rotation means rotating the elements of the array by a given amount, but instead of using rotations, a swapping technique is used. We will implement recursive and iterative methods.

enter

The given array is [ 1, 2, 3, 4, 5, 6, 7].
The number of rotations by which we have to rotate is 3. 

Output

[4, 5, 6, 7, 1, 2, 3]

illustrate

We can use the exchange algorithm and get the result, we will implement it in the next section.

Recursive method

In this approach we will try to assume that we have two arrays, the first array has size of given number of rotations and the other has size of total size minus given number of elements.

If the size of the first array is small then we will swap the elements of the first array and the last element is equal to the size of the first array, if the size of the first array is larger we will swap the first array elements is equal to the size of the second array of the given array.

For the remaining elements, we will call the recursive function by changing the swap array.

Example

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   
   // special case when the number of elements to rotate 
   // is half of the size of the given array
   if(n == 2*k){
      arr = swap(arr, 0, n - k, k);
      return;
   }		
   
   // if the first part is short	
   if(2*k < n) {
      arr = swap(arr, 0, n - k, k);
      rotate(arr, k, n - k);	
   }
   else{	
   
      // if second part is short
      arr = swap(arr, 0, k, n - k);
      rotate(arr + n - k, 2 * k - n, k);
   }
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

//Defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

Time and space complexity

The time complexity of the above code is N, where N is the size of the given array.

The space complexity of the above code is N, but this is only if we consider the memory occupied by the recursive stack.

Iteration method

The iterative method is the same as the recursive method, the only difference is that we work in a while loop instead of using recursive calls. Let's look at the code.

Example

function swap(arr, st, si, k){    
   // function to traverse over the array and swap the elements 
   for(var i = 0; i < k; i++) {
      var temp = arr[st + i];
      arr[st + i] = arr[si + i];
      arr[si + i] = temp;
   }
   return arr;
}
function rotate(arr, k, n){

   // if the number of rotations is zero or equal to the size of array
   // in this case we don't have to rotate the array 
   if(k == 0 || k == n){
      return;
   }
   var i = k;
   var j = n - k;
   while (i != j){
      if(i < j){
      
         // if the first array is shorter 
         arr = swap(arr, k - i, k + j - i, i);
         j -= i;
      }
      else{ 
      
         // if the second array is shorter 
         arr = swap(arr, k - i, k, j);
         i -= j;
      }
   }
   arr = swap(arr, k - i, k, i);
}

// function to print the given array 
function print(arr){
   var temp = "";
   for(var i = 0; i < arr.length; i++){
      temp += arr[i] + " ";
   }
   console.log(temp);
}

// defining the array 
var arr = [1, 2, 3, 4, 5, 6, 7];
var num = 3;
console.log("The given array is: ");
print(arr);

// rotating the array 
rotate(arr, num, arr.length);
console.log("The given array after " + num + " number of rotations is: ")
print(arr);

Time and space complexity

The time complexity of the above code is N, where N is the size of the given array.

The space complexity of the above code is 1 or constant because we are not using any extra space here.

in conclusion

In this tutorial, we implemented a JavaScript program to rotate an array a given number of rotations by using the block swap algorithm. We implemented the block swap algorithm using an iterative approach with O(N) time and O(1) space complexity, while using a recursive approach with O(N) space complexity.

The above is the detailed content of JavaScript program for block swapping algorithm for array rotation. For more information, please follow other related articles on the PHP Chinese website!