Randomized In-place algorithm JavaScript implementation

What is a In-place algorithm?

It means that the algorithm does not require any extra space. For example Quick Sort is in-place as it shuffles elements in the given array itself. But Merge Sort is out of place algorithm as it requires 2 temporary arrays at a time.

Now let’s come to the Randomized in-place problem

So, In this problem we are going to shuffle elements of an array without using any extra space i.e we are going to use the same original array to do the manipulation.

Algorithm: Each element of the original array is swapped with a random element in the rest elements.

here we defined a getRndInteger function which is used to get random number between min and max where min and max are included, Math.random() returns a floating value less that between 0 and 1 in floating point.

Another function we defined is swapArrayEl which is taking two array indexes, first one is from 0 to n and the other one is a random number between i and n-1 generated using our getRndInteger function.

Time complexity: O(n)

function swapArrayEl(a,b)
{
	temp = A[a];
	A[a] = A[b];
	A[b] = temp;
} 

function getRndInteger(min, max) {
	return Math.floor(Math.random() * (max - min + 1) ) + min;
}

A = [0,1,2,3];
n = A.length;

for(var i = 0; i < n; i++)
{
	swapArrayEl(i, getRndInteger(i, n-1));
}

console.log(A);