0:02

Next we're going to look at an easy application of sorting to 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 and 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 a real numbers that are generated uniformly at random. And

Â that's just means that it's well shuffled that every possible way of shuffling the

Â deck appears with the equal probability. That's fine but it requires a sort and a

Â 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. It only require a linear time to get the job done. Let's look at the

Â demo. The idea this 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

Â 0 and i uniformly at random and, and swap a[i] with that integer. So, let's

Â look at the beginning, we don't do anything just swap it with itself. Now,

Â with i = 2 or i pointing to the second card we generate a random integer in

Â between 0 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, 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 shuffled there

Â uniform, randomly shuffled. On this case, i and r are the same. There's no swap.

Â 3:03

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

Â through 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 will be between 0 and i-1. You'll

Â often see programmers thinking that they're implementing a shuffle and they

Â just choose for every entry, they just choose random place in the array to

Â exchange it with and that doesn't really work. You could do the items between i and

Â n-1, the ones that you haven't seen yet and that would also work but doing a

Â whole array doesn't give you a uniformly random result. So, with that one caveat,

Â this code is almost trivial. And it's a method in our standard random class. Now

Â if you're going to be using random methods that depend on randomness in real

Â applications, you do have to be careful. So this is 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 and that's pretty similar to our code but it's

Â actually got a few bugs, more than a few bugs. So first one is the way that random

Â works it's actually never gets to 52 which means that the last card just stays it 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

Â as we just pointed out that's not uniform. Should be between 1 and i or between

Â i+1 and 52. Another problem is in this implementation that the random uses

Â just a 32 bit seed that if you do that, there's not enough possible shuffles. The

Â number of possible shuffles is, is, is much more, if n, if n is 52, it's 52

Â factorial which is a lot bigger than two to the 32nd. So, it's not close to a

Â random or uniform. And the other thing is that, the seed is just a 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 a 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, that you go ahead and do

Â so. And the famous quote in this 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 these various tests available to make sure that

Â it's random and you'd better use 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

Â