Last week I thought about how could we shuffle an array in Javascript? Then I decided to investigate the matter. I found some interesting means by which we could achieve this. We are going to look at five ways to shuffle an array with Javascript, in no particular order let's dive in.
Custom Sort Function
The easiest way to go about this is to use a custom sort function, the array prototype in Javascript has a method called sort, this method is normally used to sort the items inside an array.
const array = [4, 2, 1, 3];
const sortedArray = array.sor((a, b) => a + b);
console.log(sortedArray) // [1, 2, 3, 4]
The above snippet demonstrates how to use the sort function in a normal instace, to generate a shuffled array we can take advantage of this sort function.
const array = [4, 2, 1, 3, 6, 5]
const shuffledArray = array.sort((a, b) => 0.5 - Math.random())
console.log(shuffledArray) // [2, 1, 3, 4, 6, 5]
This piece of code uses the Array.sort() method to shuffle an array of numbers at random. The comparison function used for the sort returns a value that is either negative, positive, or 0 and uses the Math.random() method to generate a random number between 0 and 1. The two numbers in the array will be switched if the random number is less than 0.5, in which case the comparison function will return a negative value. This will cause the array to be randomly shuffled.
The fundamental disadvantage of this approach is that a really random shuffled array cannot be relied upon to be produced. There is a potential that the array will be shuffled in a way that is not random because the comparison method only returns a value that is either negative, positive, or zero. This approach is also inefficient because each shuffle necessitates sorting the entire array.
Using a different algorithm, such as the Fisher-Yates shuffle algorithm, would be one way to overcome this flaw. This approach creates a more random shuffle by using a loop to randomly select elements from the array and swap them with the current element. This algorithm is also more effective because the shuffle is finished after just one pass around the array.
Fisher-Yates Shuffle Algorithim
The Fisher-Yates shuffle algorithm was first proposed by Ronald Fisher and Frank Yates in 1938. It is an efficient algorithm that produces a random shuffling of an array in a single pass. Since its inception, the algorithm has been used in many different applications, such as shuffling decks of cards or generating random permutations.
The Fisher-Yates shuffle algorithm works by looping through the array from the last index to the first index. For each loop, a random index is selected from the array and the current element is swapped with the element at the randomly selected index. This results in a more random shuffling of the array.
function shuffle(array) {
// Loop through array starting at the last index
for (let i = array.length - 1; i > 0; i--) {
// Generate a random index from 0 to i
const j = Math.floor(Math.random() * (i + 1));
// Swap elements at indexes i and j
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
const array = [4, 2, 1, 3, 6, 5]
console.log(shuffle(array)) // [6, 3, 4, 5, 2, 1]
console.log(shuffle(array)) // [1, 5, 4, 2, 3, 6]
The Fisher-Yates algorithm is bound to generate a completely shuffled array each time it is used, however if you want a more simplified algorithim, then you could use the Durstenfeld's version of the Fisher-Yates shuffle algorithm.
Durstenfeld's version of the Fisher-Yates shuffle algorithm.
The Durstenfeld's version of the Fisher-Yates algorithm is a simplified version of the algorithm that was proposed by Richard Durstenfeld in 1964. This version is more efficient, as it does not require a loop through the entire array, but instead starts the loop from the last index and decrements the loop counter.
function shuffle(array) {
// Loop through array starting at the last index
for (let i = array.length - 1; i > 0; i--) {
// Generate a random index from 0 to i
const j = Math.floor(Math.random() * (i + 1));
// Swap elements at indexes i and j (single line)
[array[i], array[j]] = [array[j], array[i]];
}
return array;
}
const array = [4, 2, 1, 3, 6, 5]
console.log(shuffle(array)) // [5, 1, 3, 4, 2, 6]
The procedure begins by iterating through the array from the last index to the first index, swapping the elements at each loop's random indexes between 0 and the current position. As a result, the array is shuffled more efficiently and randomly.
The main advantage of the Durstenfeld's version of the Fisher-Yates algorithm is that it is more efficient, as it does not require a loop through the entire array to complete the shuffle. It also uses a single line of code to perform the swap operation, making it simpler and easier to read.
Inside-Out Shuffle Algorithim
The inside-out shuffle algorithm is a variation of the Fisher-Yates algorithm. It works by randomly selecting elements from the array and swapping them with the current element, but in reverse order. This results in a more random shuffling of the array and is more efficient since it only requires a single pass through the array.
Here is a code example of the inside-out shuffle algorithm in Javascript:
function shuffle(array) {
// Loop through array starting at the first index
for (let i = 0; i < array.length; i++) {
// Generate a random index from i to the last index
const j = i + Math.floor(Math.random() * (array.length - i));
// Swap elements at indexes i and j
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
return array;
}
const array = [4, 2, 1, 3, 6, 5]
console.log(shuffle(array)) // [4, 1, 5, 3, 2, 6]
Is this better than Durstenfeld's version of the Fisher-Yates shuffle algorithm?
It is difficult to say definitively which algorithm is better, as both algorithms produce a random shuffling of the array. However, the inside-out shuffle algorithm is more efficient, as it only requires a single pass through the array, whereas the Durstenfeld's version requires a loop through the entire array. Additionally, the inside-out shuffle algorithm is simpler and easier to read.
Sattolo's shuffle algorithm
The Sattolo's shuffle algorithm is a variation of the Fisher-Yates algorithm that guarantees an unbiased permutation. It works by looping through the array and swapping the current element with a randomly selected element from the array, but only if the randomly selected element is not the same as the current element. This results in a more random shuffling of the array and ensures that the permutation is unbiased. The Sattolo's shuffle algorithm was devised by Carlo Sattolo in 1986.
The main benefit of the Sattolo's shuffle algorithm is that it guarantees an unbiased permutation. This means that each element in the array has an equal chance of being at any position in the array. Additionally, the algorithm is more efficient than the Fisher-Yates algorithm, as it only requires a single pass through the array to complete the shuffle.
function shuffle(array) {
// Loop through array
for (let i = 0; i < array.length; i++) {
// Generate a random index from 0 to the last index
let j = Math.floor(Math.random() * array.length);
// Swap elements at indexes i and j if they are not the same
if (i !== j) {
const temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
return array;
}
const array = [4, 2, 1, 3, 6, 5]
console.log(shuffle(array)) // [3, 1, 4, 5, 2, 6]
The main drawback of the Sattolo's shuffle algorithm is that it is not as random as the other algorithms, as it prevents the same element from being swapped with itself. Additionally, the algorithm is slightly less efficient than the other algorithms, as it requires an extra check to make sure that the randomly selected element is not the same as the current element.
Here we have 5 ways which we can shuffle an array in Javascript, to read more articles like this visit Netcreed
Top comments (2)
Information Processing Letters
Volume 22, Issue 6, 30 May 1986, Pages 315-317
Information Processing Letters
An algorithm to generate a random cyclic permutation
Sandra Sattolo
(sciencedirect.com/science/article/...)
the name of the author of Sattolo's algorithm is Sandra, she is a female!