Next, we're going to look at an easy application of sorting to a related problem called shuffling. So, suppose you have a deck of cards, one of the things that you might want to try to do is to simply rearrange those cards into random order, that's called shuffling. Here's a way to get shuffling done using a sort, it seems like the opposite. The idea is just generate a random real number for every array entry, and then sort using those random numbers as the keys. That's an effective way to get things shuffled. And it's possible to prove that that produces a uniformly random permutation of the input if there's no duplicate values, assuming that you have real numbers that are generated uniformly at random. And that just means that it's well shuffled, that every possible way of shuffling the deck appears with equal probability. That's fine, but it requires a sort, sort seems like a lot of work for this problem. And the question is, can we do better? Can we have a faster way to shuffle? Do we really need to pay the cost of a full sort? The answer to that question is, no. There's actually a very easy way to rearrange an array so that the result is a uniformly random permutation, and only require linear time to get the job done. Let's look at a demo. The idea is to pass through the array from left to right with an index i, as we've been doing. But now, we start with the array in order, and actually it doesn't matter how we start the array. And every time we pick an integer between zero and i uniformly at random, and swap a of i with that integer. So let's look at the beginning, we don't do anything, we just swap it with itself. Now with i equals two, i pointing to the second card, we generate a random integer between zero and i. In this case, it's the one to the left and we swap those. Increment i, generate a random integer, this time it's going to be the first one again, swap them. Increment i, generate a random integer, swap them. Increment i, generate a random integer, swap them. And continue in that way, swap. So for every i, we do exactly one swap. Now, a card could be involved in more than one swap, but that's not an issue. The point is that the cards to the left of i are uniform randomly shuffled. In this case, sign are the same, there is no swap. Increment i, generate a random r, swap them. And at the end, we have the deck shuffled. That's a linear time shuffling algorithm making use of randomness. It was proved actually a long time ago even before computer implementations that if you do that, you get a uniformly random permutation and it only takes linear time. So, that's definitely a way to get a deck shuffled quite easily, easy to implement. Now, it's key that the uniform random number be between zero and i minus one. You'll often see programmers thinking that they're implementing a shuffle and for every entry, they just choose a random place in the array to exchange it with, and that doesn't really work. You could do the items between i and minus one, the ones you haven't seen yet, and that would also work. But, doing the whole array doesn't give you a uniformly random result. So, with that one copied at this code, it's almost trivial and it's a method in our standard random class. Now, if you're going to be using methods that depend on randomness in real applications, you do have to be careful. So, this isn't just an example about software security, there's a lot of difficult and deep issues to worry about in software security, and we're not going to worry about all of them. But one thing that we can do is make sure that our algorithms work as advertised. So, here's an example of an implementation for online poker. Here's the code that you can find on the web for how to shuffle a deck of cards, that's pretty similar to our code but it's actually got more than a few bugs. So, our first one is, the way that random works, it actually never gets to 52, which means that the last card can end up in the last place, so it's definitely not shuffled because of that. Maybe that one's minor but it also is picking a random card from the whole deck, and as we just pointed out, that's not uniform, it should be between one and i or between i plus one and 52. Another problem is in this implementation, the random uses just a 32-bit seed, if you do that, there's not enough possible shuffles. The number of possible shuffles is much more and it's 52, it's 52 factorial which is a lot bigger than two to the 32nd, so it's not close to random or uniform. The other thing is that the seed is just the number of milliseconds since midnight and that cuts down the number of shuffles even more. And in fact, it didn't take that much hacking for someone to realize that after seeing five cards and figuring out what the server clock was doing, you could get all the future cards in real time in a program, and that's a pretty tough thing to have happen if you're implementing online poker. You might want to make sure that if you're advertising that you're doing a random shuffle, then you go ahead and do so. A famous quote and there's many similar quotes, 'The generation of random numbers is too important to be left to chance'. So, if your business does depend on shuffling, people have looked at all sorts of options, including using hardware random number generators, and there's various tests available to make sure that it's random. And you better use a good shuffling code, that's our topic. But the bottom line is, don't think that it's easy to shuffle a deck of cards. So, that's shuffling our first non-trivial sorting application.
