Shuffle an array

[00:00] The key property of a perfect shuffle is that each item should have an equal probability to end up in any index. That is, for n positions each item should have an 1/n probability for any given position. Before we jump into code, let's run through an example of the algorithm that we are going to implement.

[00:24] Let's say, we have items A, B,C, D, E. The algorithm is simply going to pick a random item, put it in position zero. Take any of the remaining items and put that in position one. Then, pick any of the remaining items and put that in position two, and so on till we have shuffled all the items.

[00:49] It is actually very easy to do mathematical analysis of this algorithm and prove its correctness. Let's say, we have n items to shuffle. If we randomly pick an element and move it to position zero, it will imply that each item has an equal 1/n probability of being in position zero.

[01:09] The probability of an element making its way to position one is equal to the probability of it not making its way to the position zero, which is n-1/n times the probability of making its way into position one, which is 1/ remaining n-1 items. The n-1 cancel each other out nicely giving us a probability a 1/n for the item to appear in position one.

[01:38] Similarly for position two, the probability is n-1/n for having skipped position zero, n-2/n-1 for having skipped position one, and 1/n-2 for having made it into position two.

[01:54] Once again, all that we are left with after multiplication is 1/n. This process continues for all the remaining positions giving us a uniform 1/n probability for an item to appear in any given position.

[02:10] With mathematical analysis out of the way, let's discuss a bit of the pseudo-code for the algorithm. We start off with our input array having an empty shuffled position, and a full and shuffled position.

[02:22] We then move through the elements of the array. In each iteration i, we simply put a random item from the unshuffled position into the ith position within the shuffled position. Hence, increasing the length of the shuffled position. This way we eventually end up with a fully shuffled array.

[02:45] Let's implement this algorithm here in TypeScript. We start by bringing in a random int function from a previous lesson. We then go ahead and create a function which takes an array of type T and returns an array of type T.

[03:03] Within the function body, we go ahead and make the copy of the array. Note that if we don't do this the algorithm can inbuilt essentially operate in place. Next, we simply loop through the input array. In each iteration, we randomly pick an index from any of the remaining unshuffled items.

[03:23] We then swap, putting the randomly chosen item into the arrays ith position. Finally, after the loop we return the shuffled array. Shuffling is one of those algorithms when the correct answer is blindingly simple, if you have done it before.

[03:40] What we implemented here is called the modern version of the Fisher-Yates shuffle. Since it only loops through the array once, it operates in linear time that is as On time complexity.