Now there are a lot of algorithmic questions that are related to randomization, but the most popular one that I can think of is the problem of shuffling, for example, shuffling a deck of cards. And that is the problem that we will look at in this lesson. So let's go. Now before we look at anything else, the first thing that we need to clarify is the concept of the perfect shuffle. What a perfect shuffle essentially means is that any item can appear in any position with equal probability. So if we have N items in end positions, then any item can appear in any position

with the probability one over end. Now, that might sound like a hard ask, but it's actually quite easy to achieve. Fundamentally, we pick an item one by one and put it in the output. So assuming we have an array, A, B, C, D, F, whatever, we pick an item at random. Let's say we pick C and we put it in position zero and we pick a next random item. Let's say we pick D, put it in position one, and then pick the next random item and so on. And we can actually prove the mathematical correctness of this algorithm quite easily. So let's do that next.

Now, since we're going to pick the first item at random, the odds of it getting picked are going to be quite fair. It's going to be simply one over N. As we have N items, things get a bit more interesting when we pick up the next item at index one. The odds of it getting picked are essentially the odds of it not getting selected in the first attempt and getting selected in the second attempt. Now, the odd of it not getting selected in the first attempt are actually quite high as we have N minus one items that will not get picked among the N items. The odds of it getting picked in the second attempt is simply going to be one over the N minus one.

Items that we will be picking amongst the N minus ones will cancel out with each other, leaving us with the standardized one over N. And this process will continue for all other attempts as well. Only the chain of the item not getting in into nth attempts will get longer. However, we will always be left with one on top and N at the bottom. So with the mathematical analysis of picking an item randomly one by one out of the way, let's look at our example once more. Our objective is to randomly select the items one by one. However, there is one more complication that we need

to think of at each step. We have to remember which items we have already picked and which items are still available to be randomly chosen. Now, we could do this in separate data structures, however, it's actually quite easy to do in a single array. So let's look at an example. We will essentially have the array as a shuffle and an un shuffle portion. We start off with a completely empty shuffled portion. So in our first attempt, let's say we pick C, move it into index zero, and we take whatever was there, for example, in this case it is A,

and move it into where C originally was. Now we have this shuffle portion containing C and this uns shuffle portion containing all the other members. And the next item we pick, we will pick randomly starting at index one all the way Till N. Let's say we pick T, we swap what was already there, which is the character B, and move it into where D was. So in each step, the shuffle portion gets bigger and bigger till we eventually run out of all the uns shuffled members. And then we have a completely shuffled array. Now understanding how the algorithm works might have been a

bit involved, but quoting it up is actually going to be quite easy. We start off by bringing in our random integer function, which we coded up in our previous lesson. And then we have this template function, which will take an array of type T and return an array of type T. And the first thing that we will do is that we will create a copy of the input array as I don't like mutating our input arrays. However, if you'd lead this call to slice this algorithm will still work perfectly fine. It's just that the input array is what we will be shuffling in place. Now for the main core of the algorithm, we simply have to loop through end times for an items.

And in each iteration, the first thing that we do is we get a random index starting at I all the way till the end of the array, and then we swap the item at the random index with the item at the I index. This means that the array has been shuffled up till I, and then the loop continues with i plus plus. This one line swapping of I item with the random index item is a JavaScript trick that I have a lesson dedicated to as well, if you are interested. Now, once this loop terminates, we've essentially placed N items into N positions, which is exactly what we want our shuffle algorithm to do.

Now because we are only looping to the input array once the time complexity of this algorithm is OFN. And because we are creating a new array with array to slice the space, complexity is OFN. However, if you remove this call to slice, we can essentially shuffle the input array in place, therefore giving us a space complexity of OF one, which is constant. Now shuffling is a very well understood problem, and the algorithm that we implemented in this lesson is known as the modernized version of the Fisher Yates Shuffle.