Fisher-Yates Shuffle Algorithm

My blog is now located at http://www.WhoIsSethLong.com

I went to an interview recently and was asked to arrange an array of integers from 1 to 52 in random order.  As soon as they said 52 I thought about a deck of cards, then instantly thought about the Fisher-Yates Shuffle Algorithm.

The Fisher-Yates Shuffle Algorithm is a simple algorithm that runs in linear time and is used to shuffle an array in random order.  The algorithm loops through each item in the array, generates a random number between 0 and the array length, then assigns the array item to the randomly generated array position.  This is a simple algorithm and is probably easiest understood with an example. For this example I’ll use C#.

public void FisherYates(int[] ary)
{
    Random rnd = new Random();

    for (int i = ary.Length - 1; i > 0; i--)
    {
        int r = rnd.Next(0, i);

        int tmp = ary[i];
        ary[i] = ary[r];
        ary[r] = tmp;
    }
}

There are other ways to sort the array besides the Fisher- Yates method.  If this had been a deck of cards, another method would be to assign a randomly generated 64-bit number to each card then sort by their randomly assigned number.

- Seth Long

About these ads