In-Place Shuffle

To shuffle an array in-place, we must first create a function to generate a random number between two numbers. An in-place function modifies an object directly so that no extra data space must be used.

Using Math.random(), we can generate a random number. Thus our random function will look like this:

function getRandom(floor, ceiling) {
  return Math.floor(Math.random() * (ceiling - floor + 1)) + floor;
}

In order to shuffle the array elements in place, we must swap elements in order to maintain the same space complexity. So, we’ll iterate over each element in the array and swap it with an element at a random index.

for (let indexWeAreChoosingFor = 0; indexWeAreChoosingFor < array.length - 1; indexWeAreChoosingFor++) {
    const randomChoiceIndex = getRandom(indexWeAreChoosingFor, array.length - 1);
    if (randomChoiceIndex !== indexWeAreChoosingFor) {
      const valueAtIndexWeChoseFor = array[indexWeAreChoosingFor];
      array[indexWeAreChoosingFor] = array[randomChoiceIndex];
      array[randomChoiceIndex] = valueAtIndexWeChoseFor;
    }
}

We generate randomChoiceIndex at each index by passing getRandom a floor of the current index, in order to not swap the current element with one previously placed.

This is a form of the greedy algorithm, because we’re choosing the best looking option at every iteration.