# Fisher-Yates shuffle

### 27 January, 2020 - 3 min read

# Weekend progress

Ok, I digress. From now on, I will say 'no-zero' weekdays. Weekends are off limits. Today is monday and I 'accidentally' learnt about an algorithm. I built a matching game a few weeks before and used a shuffle method that I got from StackOverflow, you can play it here Matching Game.

I wanted to understand it fully instead of just copying and pasting, turns out it is called the Fisher-Yates shuffle.

```
function shuffle(array) {
console.log("array before" ,array)
var currentIndex = array.length,
temporaryValue,
randomIndex;
while (currentIndex !== 0) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
```

Acoording to Wikipedia : The Fisher–Yates shuffle is an algorithm for generating a random mix of a finite sequence—basically, the algorithm shuffles the sequence. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the algorithm is efficient: it takes time proportional to the number of items being shuffled and shuffles them in place.

## Algorithm steps

- According to this algorithm we should loop the array from back to front. For instance, in the following example, we have an array consisting of 8 elements(A,B,C,D,E,F,G,H) from index 0 to index 7. So the first loop pass will affect the element at the last index 7 that is H.
- Next step is to generate a random number (random index) between the selected index 7 and index 0. For suppose let the random index be 3.
- After getting the random index swap the elements that are in the selected index and at random index.The element at the random index in the provided array is D. So after swapping, the array will be changed to A,B,C,H,E,G,F,D.
- In the second loop pass just ignore the last index (since it is already looped) and try to find the random index between index 0 and index 6 that is between the elements A and F. *Let the generated random index be 2.
- After getting the random index let's swap the elements at indexes at 6 and 2. Now the array will look as A,B,F,H,E,G,C,D.
- This algorithm follows the same pattern that is it ignores index 6 and starts finding random index between index 5 and index 0 and so on until it reached the index 1. It can't take index 0 to loop because there are no indexes less than 0 for swapping purpose.
- Note that there is a possibility that generated random index be selected loop index. For instance, let the loop is running between selected index 4 and index 0. let the random index generated be 4. Then the value at the index 4 will remain at the same position.