Array rotation, a simple approach using JS

What's an array?

An array is a type of linear data structure containing a collection of elements of similar data type. Arrays are one of the most important data structures. The elements in the array are stored in contiguous memory locations.

what's array rotation?

Array rotation is nothing but shifting elements of the array in a specified direction with a rotation factor. No worries, this will be made clear with an example below,

	// let this be the initial stage, and assume we have to rotate it to left by a rotation factor of 1.
	let arr = [1,2,3,4,5];

	// The below array is the rotated array.
	let arr1 = [2,3,4,5,1]

view raw Array.js hosted with ❤ by GitHub

Reversal algorithm for array rotation

There are many ways to rotate an array, you may use a temporary array to store values and then replace them in the actual array, or you may store the first element of the array in a temporary variable. Shift the other elements to the left, and we have to do this for d times (where d is the rotation factor). We are going to use Reversal algorithm for rotating the array in left direction.

How the Reversal algorithm works?

Unlike other methods mentioned above, Reversal algorithm don't use any temporary variable or array for the rotation process. This makes it more space efficient. This algorithm works on 3 steps. They are,

reverse d elements.
reverse n-d elements.
And finally, reverse n elements.

Example:

	// sample array
	let samparr = [1,2,3,4,5];

	// step 1 -> reverse d elements.
	let samparr = [2,1,3,4,5];

	// step 2 -> reverse n-d elements. Here n=5 and d=2 so (n-d) = (5-2=3)
	let samparr = [2,1,5,4,3];

	// step 3 -> reverse n elements. This gives the rotated array.
	let samparr = [3,4,5,1,2]

view raw Array.js hosted with ❤ by GitHub

Code it in JS

First, we need a function to rotate the array from a given index to the end. So it takes 3 parameters like samparr, begin, end. We use a while loop and assign the starting value of samparr to a temporary variable called temp.
We then assign the starting value of samparr to the ending value of samparr. And, finally, we assign the ending value of samparr to the temp again. We use this temp variable to dynamically change the starting and ending values of the samparr. We then increment the start with 1 and decrement the end with 1. This is going to be our main function, which we would call with respect to the above-mentioned 3 steps.

	function Reverse(samparr, begin, end) {
	while (begin < end) {
	temp = samparr[begin];
	samparr[begin] = samparr[end];
	samparr[end] = temp;
	begin = begin + 1;
	end = end - 1;
	}
	}

view raw Array.js hosted with ❤ by GitHub

We, then, need a function to actually rotate the array to the left using the rotation factor d. For that, we create another function which takes the samparr, d and n as parameters and return the rotated array. We return the function if we have d=0, which means the array is empty. Going good till now, but wait!, What if the d is greater than n, step 2 will become broken, to fix that, we just update d as d % n. We'll look at an example in a minimum scale to better understand this d % n

	// let us have an array of n = 3 and d = 4
	let samparr = [1,2,3];

	// step 1 -> reverse d elements.
	let samparr = ["out of bounds"]

	// To resolve this we refactor d as d = d % n,
	// so d becomes 1 and 1<n so we rotate the array with d as 1.
	let samparr = [1,2,3];

	// step 2 -> reverse n-d elements.
	let samparr = [1,3,2];

	// step 3 -> reverse n elements. we get the rotated array.
	let samparr = [2,3,1]

view raw Array.js hosted with ❤ by GitHub

Step1

Step2

Step3

Reverse

	function Rotate(samparr, d, n) {
	if (d == 0) {
	return;
	}
	Reverse(samparr, 0, d - 1);
	Reverse(samparr, d, n - 1);
	Reverse(samparr, 0, n - 1);
	}

view raw Array.js hosted with ❤ by GitHub

So, Finally, we have to console log the rotated array. For that, we create a function called Logger, which will console log the rotated array. This function takes two parameters, samparr and n. It is a simple function which loops through all elements in the array and log them onto console.

	function Logger(samparr, n) {
	for (i = 0; i < n; i++) {
	console.log(samparr[i]);
	}
	}

view raw Array.js hosted with ❤ by GitHub

Hurray 🎉

It's done. The last and final thing we do is pass inputs to our functions, to see them in action.

	function Reverse(samparr, begin, end) {
	while (begin < end) {
	temp = samparr[begin];
	samparr[begin] = samparr[end];
	samparr[end] = temp;
	begin = begin + 1;
	end = end - 1;
	}
	}

	function Rotate(samparr, d, n) {
	if (d == 0) {
	return;
	}
	Reverse(samparr, 0, d - 1);
	Reverse(samparr, d, n - 1);
	Reverse(samparr, 0, n - 1);
	}

	function Logger(samparr, n) {
	for (i = 0; i < n; i++) {
	console.log(samparr[i]);
	}
	}

	let inparray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
	let n = inparray.length;
	let d = 5
	Rotate(inparray, d, n);
	Logger(inparray, n)