Shuffling Algorithms
By: samanddeanus@yahoo.com

"Algorithm -- a formal term for Al Gore getting his groove on."

There are different ways to randomly permute an array (shuffle a deck of cards).

One method -- Fifty-two pickup shuffle:

One way: write out all the numbers on punch cards. Someone drops the punch cards on the floor and then picks them and puts them in the card reader without sorting them.

Clearly, this is not the best method.

Bad method:
DIM A(1 TO 52)
FOR I=1 TO 52
 A(I)=I
NEXT
FOR I=1 TO 52
 N = INT(RND(1)*52)+1
 SWAP A(I), A(N)
NEXT

This method is bad because not all permutations are equally likely: there are n^n different execution paths but only n! permutations (where n is the number of cards).  n! is not a divisor of n^n so not all permutations are equally likely.

The simplest method is to assign a random number between 0 and 1to every card and then sort the deck based on these random numbers.  It is easy to see why this works: each number is equally likely to go to any position in the array. However, there is a faster way [O(n) vs O(n log n)]:

DIM A(1 TO 52)
FOR I=1 TO 52
 A(I)=I
NEXT
N=52
DO
 K = INT(RND(1)*52)+1
 IF K<>N THEN SWAP A(K), A(N)
 N=N-1
LOOP UNTIL N<2

Note that the first method might be slower then O(n log n) if the programmer uses a O(n^2) algorithm like bubble sort or insertion sort.

However, for a 52-card deck, it probably doesn't make much of a difference.