Skip to main content

Block swap algorithm for array rotation

The block swap algorithm is a popular method for rotating an array in-place. It works by dividing the array into two blocks, and then swapping the elements of these blocks in a specific way to achieve the desired rotation.

Let's say we have an array of length n and we want to rotate it by k positions. We first divide the array into two blocks, A and B, where A contains the first k elements of the array and B contains the remaining n-k elements.

To perform the rotation, we swap the elements of A and B in the following way:

  1. Swap the first element of A with the first element of B.
  2. Swap the second element of A with the second-to-last element of B.
  3. Swap the third element of A with the third-to-last element of B.
  4. Continue this pattern, swapping the i-th element of A with the (n-k+i)-th element of B, until we have swapped all k elements of A with their corresponding elements in B.

After performing these swaps, the array will be rotated by k positions. The time complexity of this algorithm is O(n), as we only need to perform n swaps.

It is worth noting that this algorithm only works if k is less than n. If k is greater than or equal to n, we can simply take the remainder of k when divided by n and perform the rotation using that value instead.

Code Solution

// C program for 
// Block swap algorithm for array rotation
#include <stdio.h>

// This is display the given array elements
void printData(int arr[], int n)
{
	// Executing the loop through by the size of array
	for (int i = 0; i < n; ++i)
	{
		printf("  %d", arr[i]);
	}
	printf("\n");
}
// This is swapping given block elements
void swapSubArray(int arr[], int s, int e, int n)
{
	// Executing the loop through by the n 
	for (int i = 0; i < n; i++)
	{
		// Swap array element
		arr[s + i] = arr[s + i] + arr[e + i];
		arr[e + i] = arr[s + i] - arr[e + i];
		arr[s + i] = arr[s + i] - arr[e + i];
	}
}
void blockSwapAlgo(int arr[], int n, int k)
{
	if (k == 0 || k >= n)
	{
		// When k = 0 then result are not change
		// And k >= n is greater than or equal to size n
		return;
	}
	// Display given array
	printf("\n Before rotation  ");
	printf("\n Array : ");
	printData(arr, n);
	printf(" Given rotation k is : %d", k);
	int i = k;
	int j = n - k;
	while (i != j)
	{
		if (i < j)
		{
			// When i is less than j
			swapSubArray(arr, k - i, k + j - i, i);
			// Reduce i in j
			j = j - i;
		}
		else
		{
			// When j is less than i
			swapSubArray(arr, k - i, k, j);
			i = i - j;
		}
	}
	swapSubArray(arr, k - i, k, i);
	// Display resultant array
	printf("\n After rotation  ");
	printf("\n Array : ");
	printData(arr, n);
}
int main(int argc, char const *argv[])
{
	// Array of integer elements
	int arr[] = {
		8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	// Test case
	blockSwapAlgo(arr, n, 5);
	blockSwapAlgo(arr, n, 3);
	return 0;
}

input

 Before rotation
 Array :   8  7  6  5  4  3  2  1  0
 Given rotation k is : 5
 After rotation
 Array :   3  2  1  0  8  7  6  5  4

 Before rotation
 Array :   3  2  1  0  8  7  6  5  4
 Given rotation k is : 3
 After rotation
 Array :   0  8  7  6  5  4  3  2  1
/*
  Java Program for 
  Block swap algorithm for array rotation
*/
public class Rotation
{
	// This is display the given array elements
	public void printData(int[] arr, int n)
	{
		// Executing the loop through by the size of array
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	// This is swapping given block elements
	public void swapSubArray(int[] arr, int s, int e, int n)
	{
		// Executing the loop through by the n 
		for (int i = 0; i < n; i++)
		{
			// Swap array element
			arr[s + i] = arr[s + i] + arr[e + i];
			arr[e + i] = arr[s + i] - arr[e + i];
			arr[s + i] = arr[s + i] - arr[e + i];
		}
	}
	public void blockSwapAlgo(int[] arr, int n, int k)
	{
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		System.out.println(" Before rotation ");
		System.out.println(" Array : ");
		printData(arr, n);
		System.out.println(" Given rotation k is : " + k);
		int i = k;
		int j = n - k;
		while (i != j)
		{
			if (i < j)
			{
				// When i is less than j
				swapSubArray(arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				swapSubArray(arr, k - i, k, j);
				i = i - j;
			}
		}
		swapSubArray(arr, k - i, k, i);
		// Display resultant array
		System.out.println(" After rotation ");
		System.out.println(" Array : ");
		printData(arr, n);
      	System.out.print("\n");
	}
	public static void main(String[] args)
	{
		Rotation task = new Rotation();
		// Array of integer elements
		int[] arr = {
			8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
		};
		// Get the number of elements
		int n = arr.length;
		// Test case
		task.blockSwapAlgo(arr, n, 5);
		task.blockSwapAlgo(arr, n, 3);
	}
}

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 3 2 1 0 8 7 6 5 4

 Before rotation
 Array :
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation
 Array :
 0 8 7 6 5 4 3 2 1

// Include header file
#include <iostream>
using namespace std;
/*
  C++ Program for 
  Block swap algorithm for array rotation
*/
class Rotation
{
	public:
		// This is display the given array elements
		void printData(int arr[], int n)
		{
			// Executing the loop through by the size of array
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
			cout << "\n";
		}
	// This is swapping given block elements
	void swapSubArray(int arr[], int s, int e, int n)
	{
		// Executing the loop through by the n 
		for (int i = 0; i < n; i++)
		{
			// Swap array element
			arr[s + i] = arr[s + i] + arr[e + i];
			arr[e + i] = arr[s + i] - arr[e + i];
			arr[s + i] = arr[s + i] - arr[e + i];
		}
	}
	void blockSwapAlgo(int arr[], int n, int k)
	{
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		cout << " Before rotation " << endl;
		cout << " Array : " << endl;
		this->printData(arr, n);
		cout << " Given rotation k is : " << k << endl;
		int i = k;
		int j = n - k;
		while (i != j)
		{
			if (i < j)
			{
				// When i is less than j
				this->swapSubArray(arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				this->swapSubArray(arr, k - i, k, j);
				i = i - j;
			}
		}
		this->swapSubArray(arr, k - i, k, i);
		// Display resultant array
		cout << " After rotation " << endl;
		cout << " Array : " << endl;
		this->printData(arr, n);
		cout << "\n";
	}
};
int main()
{
	Rotation *task = new Rotation();
	// Array of integer elements
	int arr[] = {
		8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
	};
	// Get the number of elements
	int n = sizeof(arr) / sizeof(arr[0]);
	// Test case
	task->blockSwapAlgo(arr, n, 5);
	task->blockSwapAlgo(arr, n, 3);
	return 0;
}

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 3 2 1 0 8 7 6 5 4

 Before rotation
 Array :
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation
 Array :
 0 8 7 6 5 4 3 2 1

// Include namespace system
using System;
/*
  Csharp Program for 
  Block swap algorithm for array rotation
*/
public class Rotation
{
	// This is display the given array elements
	public void printData(int[] arr, int n)
	{
		// Executing the loop through by the size of array
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	// This is swapping given block elements
	public void swapSubArray(int[] arr, int s, int e, int n)
	{
		// Executing the loop through by the n 
		for (int i = 0; i < n; i++)
		{
			// Swap array element
			arr[s + i] = arr[s + i] + arr[e + i];
			arr[e + i] = arr[s + i] - arr[e + i];
			arr[s + i] = arr[s + i] - arr[e + i];
		}
	}
	public void blockSwapAlgo(int[] arr, int n, int k)
	{
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		Console.WriteLine(" Before rotation ");
		Console.WriteLine(" Array : ");
		this.printData(arr, n);
		Console.WriteLine(" Given rotation k is : " + k);
		int i = k;
		int j = n - k;
		while (i != j)
		{
			if (i < j)
			{
				// When i is less than j
				this.swapSubArray(arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				this.swapSubArray(arr, k - i, k, j);
				i = i - j;
			}
		}
		this.swapSubArray(arr, k - i, k, i);
		// Display resultant array
		Console.WriteLine(" After rotation ");
		Console.WriteLine(" Array : ");
		this.printData(arr, n);
		Console.Write("\n");
	}
	public static void Main(String[] args)
	{
		Rotation task = new Rotation();
		// Array of integer elements
		int[] arr = {
			8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 , 0
		};
		// Get the number of elements
		int n = arr.Length;
		// Test case
		task.blockSwapAlgo(arr, n, 5);
		task.blockSwapAlgo(arr, n, 3);
	}
}

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 3 2 1 0 8 7 6 5 4

 Before rotation
 Array :
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation
 Array :
 0 8 7 6 5 4 3 2 1

<?php
/*
  Php Program for 
  Block swap algorithm for array rotation
*/
class Rotation
{
	// This is display the given array elements
	public	function printData($arr, $n)
	{
		// Executing the loop through by the size of array
		for ($i = 0; $i < $n; ++$i)
		{
			echo " ".strval($arr[$i]);
		}
		echo "\n";
	}
	// This is swapping given block elements
	public	function swapSubArray($arr, $s, $e, $n)
	{
		// Executing the loop through by the n 
		for ($i = 0; $i < $n; $i++)
		{
			// Swap array element
			$arr[$s + $i] = $arr[$s + $i] + $arr[$e + $i];
			$arr[$e + $i] = $arr[$s + $i] - $arr[$e + $i];
			$arr[$s + $i] = $arr[$s + $i] - $arr[$e + $i];
		}
	}
	public	function blockSwapAlgo($arr, $n, $k)
	{
		if ($k == 0 || $k >= $n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		echo " Before rotation ".
		"\n";
		echo " Array : ".
		"\n";
		$this->printData($arr, $n);
		echo " Given rotation k is : ".strval($k).
		"\n";
		$i = $k;
		$j = $n - $k;
		while ($i != $j)
		{
			if ($i < $j)
			{
				// When i is less than j
				$this->swapSubArray($arr, $k - $i, $k + $j - $i, $i);
				// Reduce i in j
				$j = $j - $i;
			}
			else
			{
				// When j is less than i
				$this->swapSubArray($arr, $k - $i, $k, $j);
				$i = $i - $j;
			}
		}
		$this->swapSubArray($arr, $k - $i, $k, $i);
		// Display resultant array
		echo " After rotation ".
		"\n";
		echo " Array : ".
		"\n";
		$this->printData($arr, $n);
		echo "\n";
	}
}

function main()
{
	$task = new Rotation();
	// Array of integer elements
	$arr = array(8, 7, 6, 5, 4, 3, 2, 1, 0);
	// Get the number of elements
	$n = count($arr);
	// Test case
	$task->blockSwapAlgo($arr, $n, 5);
	$task->blockSwapAlgo($arr, $n, 3);
}
main();

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 8 7 6 5 4 3 2 1 0

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 3
 After rotation
 Array :
 8 7 6 5 4 3 2 1 0

/*
  Node JS Program for 
  Block swap algorithm for array rotation
*/
class Rotation
{
	// This is display the given array elements
	printData(arr, n)
	{
		// Executing the loop through by the size of array
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	// This is swapping given block elements
	swapSubArray(arr, s, e, n)
	{
		// Executing the loop through by the n 
		for (var i = 0; i < n; i++)
		{
			// Swap array element
			arr[s + i] = arr[s + i] + arr[e + i];
			arr[e + i] = arr[s + i] - arr[e + i];
			arr[s + i] = arr[s + i] - arr[e + i];
		}
	}
	blockSwapAlgo(arr, n, k)
	{
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		console.log(" Before rotation ");
		console.log(" Array : ");
		this.printData(arr, n);
		console.log(" Given rotation k is : " + k);
		var i = k;
		var j = n - k;
		while (i != j)
		{
			if (i < j)
			{
				// When i is less than j
				this.swapSubArray(arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				this.swapSubArray(arr, k - i, k, j);
				i = i - j;
			}
		}
		this.swapSubArray(arr, k - i, k, i);
		// Display resultant array
		console.log(" After rotation ");
		console.log(" Array : ");
		this.printData(arr, n);
		process.stdout.write("\n");
	}
}

function main()
{
	var task = new Rotation();
	// Array of integer elements
	var arr = [8, 7, 6, 5, 4, 3, 2, 1, 0];
	// Get the number of elements
	var n = arr.length;
	// Test case
	task.blockSwapAlgo(arr, n, 5);
	task.blockSwapAlgo(arr, n, 3);
}
main();

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 3 2 1 0 8 7 6 5 4

 Before rotation
 Array :
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation
 Array :
 0 8 7 6 5 4 3 2 1

#  Python 3 Program for 
#  Block swap algorithm for array rotation
class Rotation :
	#  This is display the given list elements
	def printData(self, arr, n) :
		i = 0
		#  Executing the loop through by the size of list
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	#  This is swapping given block elements
	def swapSubArray(self, arr, s, e, n) :
		i = 0
		#  Executing the loop through by the n 
		while (i < n) :
			#  Swap list element
			arr[s + i] = arr[s + i] + arr[e + i]
			arr[e + i] = arr[s + i] - arr[e + i]
			arr[s + i] = arr[s + i] - arr[e + i]
			i += 1
		
	
	def blockSwapAlgo(self, arr, n, k) :
		if (k == 0 or k >= n) :
			#  When k = 0 then result are not change
			#  And k >= n is greater than or equal to size n
			return
		
		#  Display given list
		print(" Before rotation ")
		print(" Array : ")
		self.printData(arr, n)
		print(" Given rotation k is : ", k)
		i = k
		j = n - k
		while (i != j) :
			if (i < j) :
				#  When i is less than j
				self.swapSubArray(arr, k - i, k + j - i, i)
				#  Reduce i in j
				j = j - i
			else :
				#  When j is less than i
				self.swapSubArray(arr, k - i, k, j)
				i = i - j
			
		
		self.swapSubArray(arr, k - i, k, i)
		#  Display resultant list
		print(" After rotation ")
		print(" Array : ")
		self.printData(arr, n)
		print(end = "\n")
	

def main() :
	task = Rotation()
	arr = [8, 7, 6, 5, 4, 3, 2, 1, 0]
	n = len(arr)
	#  Test case
	task.blockSwapAlgo(arr, n, 5)
	task.blockSwapAlgo(arr, n, 3)

if __name__ == "__main__": main()

input

 Before rotation
 Array :
  8  7  6  5  4  3  2  1  0
 Given rotation k is :  5
 After rotation
 Array :
  3  2  1  0  8  7  6  5  4

 Before rotation
 Array :
  3  2  1  0  8  7  6  5  4
 Given rotation k is :  3
 After rotation
 Array :
  0  8  7  6  5  4  3  2  1

#  Ruby Program for 
#  Block swap algorithm for array rotation
class Rotation 
	#  This is display the given array elements
	def printData(arr, n) 
		i = 0
		#  Executing the loop through by the size of array
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	#  This is swapping given block elements
	def swapSubArray(arr, s, e, n) 
		i = 0
		#  Executing the loop through by the n 
		while (i < n) 
			#  Swap array element
			arr[s + i] = arr[s + i] + arr[e + i]
			arr[e + i] = arr[s + i] - arr[e + i]
			arr[s + i] = arr[s + i] - arr[e + i]
			i += 1
		end

	end

	def blockSwapAlgo(arr, n, k) 
		if (k == 0 || k >= n) 
			#  When k = 0 then result are not change
			#  And k >= n is greater than or equal to size n
			return
		end

		#  Display given array
		print(" Before rotation ", "\n")
		print(" Array : ", "\n")
		self.printData(arr, n)
		print(" Given rotation k is : ", k, "\n")
		i = k
		j = n - k
		while (i != j) 
			if (i < j) 
				#  When i is less than j
				self.swapSubArray(arr, k - i, k + j - i, i)
				#  Reduce i in j
				j = j - i
			else 
				#  When j is less than i
				self.swapSubArray(arr, k - i, k, j)
				i = i - j
			end

		end

		self.swapSubArray(arr, k - i, k, i)
		#  Display resultant array
		print(" After rotation ", "\n")
		print(" Array : ", "\n")
		self.printData(arr, n)
		print("\n")
	end

end

def main() 
	task = Rotation.new()
	#  Array of integer elements
	arr = [8, 7, 6, 5, 4, 3, 2, 1, 0]
	#  Get the number of elements
	n = arr.length
	#  Test case
	task.blockSwapAlgo(arr, n, 5)
	task.blockSwapAlgo(arr, n, 3)
end

main()

input

 Before rotation 
 Array : 
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation 
 Array : 
 3 2 1 0 8 7 6 5 4

 Before rotation 
 Array : 
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation 
 Array : 
 0 8 7 6 5 4 3 2 1


/*
  Scala Program for 
  Block swap algorithm for array rotation
*/
class Rotation()
{
	// This is display the given array elements
	def printData(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		// Executing the loop through by the size of array
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	// This is swapping given block elements
	def swapSubArray(arr: Array[Int], s: Int, e: Int, n: Int): Unit = {
		var i: Int = 0;
		// Executing the loop through by the n 
		while (i < n)
		{
			// Swap array element
			arr(s + i) = arr(s + i) + arr(e + i);
			arr(e + i) = arr(s + i) - arr(e + i);
			arr(s + i) = arr(s + i) - arr(e + i);
			i += 1;
		}
	}
	def blockSwapAlgo(arr: Array[Int], n: Int, k: Int): Unit = {
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		println(" Before rotation ");
		println(" Array : ");
		printData(arr, n);
		println(" Given rotation k is : " + k);
		var i: Int = k;
		var j: Int = n - k;
		while (i != j)
		{
			if (i < j)
			{
				// When i is less than j
				swapSubArray(arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				swapSubArray(arr, k - i, k, j);
				i = i - j;
			}
		}
		swapSubArray(arr, k - i, k, i);
		// Display resultant array
		println(" After rotation ");
		println(" Array : ");
		printData(arr, n);
		print("\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Rotation = new Rotation();
		// Array of integer elements
		var arr: Array[Int] = Array(8, 7, 6, 5, 4, 3, 2, 1, 0);
		// Get the number of elements
		var n: Int = arr.length;
		// Test case
		task.blockSwapAlgo(arr, n, 5);
		task.blockSwapAlgo(arr, n, 3);
	}
}

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 3 2 1 0 8 7 6 5 4

 Before rotation
 Array :
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation
 Array :
 0 8 7 6 5 4 3 2 1

/*
  Swift 4 Program for 
  Block swap algorithm for array rotation
*/
class Rotation
{
	// This is display the given array elements
	func printData(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		// Executing the loop through by the size of array
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	// This is swapping given block elements
	func swapSubArray(_ arr: inout[Int], _ s: Int, _ e: Int, _ n: Int)
	{
		var i: Int = 0;
		// Executing the loop through by the n 
		while (i < n)
		{
			// Swap array element
			arr[s + i] = arr[s + i] + arr[e + i];
			arr[e + i] = arr[s + i] - arr[e + i];
			arr[s + i] = arr[s + i] - arr[e + i];
			i += 1;
		}
	}
	func blockSwapAlgo(_ arr: inout[Int], _ n: Int, _ k: Int)
	{
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		print(" Before rotation ");
		print(" Array : ");
		self.printData(arr, n);
		print(" Given rotation k is : ", k);
		var i: Int = k;
		var j: Int = n - k;
		while (i  != j)
		{
			if (i < j)
			{
				// When i is less than j
				self.swapSubArray(&arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				self.swapSubArray(&arr, k - i, k, j);
				i = i - j;
			}
		}
		self.swapSubArray(&arr, k - i, k, i);
		// Display resultant array
		print(" After rotation ");
		print(" Array : ");
		self.printData(arr, n);
		print(terminator: "\n");
	}
}
func main()
{
	let task: Rotation = Rotation();
	// Array of integer elements
	var arr: [Int] = [8, 7, 6, 5, 4, 3, 2, 1, 0];
	// Get the number of elements
	let n: Int = arr.count;
	// Test case
	task.blockSwapAlgo(&arr, n, 5);
	task.blockSwapAlgo(&arr, n, 3);
}
main();

input

 Before rotation
 Array :
  8  7  6  5  4  3  2  1  0
 Given rotation k is :  5
 After rotation
 Array :
  3  2  1  0  8  7  6  5  4

 Before rotation
 Array :
  3  2  1  0  8  7  6  5  4
 Given rotation k is :  3
 After rotation
 Array :
  0  8  7  6  5  4  3  2  1

/*
  Kotlin Program for 
  Block swap algorithm for array rotation
*/
class Rotation
{
	// This is display the given array elements
	fun printData(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i].toString());
			i += 1;
		}
		print("\n");
	}
	// This is swapping given block elements
	fun swapSubArray(arr: Array < Int > , s: Int, e: Int, n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			// Swap array element
			arr[s + i] = arr[s + i] + arr[e + i];
			arr[e + i] = arr[s + i] - arr[e + i];
			arr[s + i] = arr[s + i] - arr[e + i];
			i += 1;
		}
	}
	fun blockSwapAlgo(arr: Array < Int > , n: Int, k: Int): Unit
	{
		if (k == 0 || k >= n)
		{
			// When k = 0 then result are not change
			// And k >= n is greater than or equal to size n
			return;
		}
		// Display given array
		println(" Before rotation ");
		println(" Array : ");
		this.printData(arr, n);
		println(" Given rotation k is : " + k.toString());
		var i: Int = k;
		var j: Int = n - k;
		while (i != j)
		{
			if (i < j)
			{
				// When i is less than j
				this.swapSubArray(arr, k - i, k + j - i, i);
				// Reduce i in j
				j = j - i;
			}
			else
			{
				// When j is less than i
				this.swapSubArray(arr, k - i, k, j);
				i = i - j;
			}
		}
		this.swapSubArray(arr, k - i, k, i);
		// Display resultant array
		println(" After rotation ");
		println(" Array : ");
		this.printData(arr, n);
		print("\n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Rotation = Rotation();
	// Array of integer elements
	val arr: Array < Int > = arrayOf(8, 7, 6, 5, 4, 3, 2, 1, 0);
	// Get the number of elements
	val n: Int = arr.count();
	// Test case
	task.blockSwapAlgo(arr, n, 5);
	task.blockSwapAlgo(arr, n, 3);
}

input

 Before rotation
 Array :
 8 7 6 5 4 3 2 1 0
 Given rotation k is : 5
 After rotation
 Array :
 3 2 1 0 8 7 6 5 4

 Before rotation
 Array :
 3 2 1 0 8 7 6 5 4
 Given rotation k is : 3
 After rotation
 Array :
 0 8 7 6 5 4 3 2 1
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment