C# Fisher-Yates Shuffle

Shuffling an array randomizes its element order. With the Fisher-Yates shuffle, first implemented on computers by Durstenfeld in 1964, we can randomly sort elements. We implement an accurate and effective shuffling method for all array types.

This C# algorithm article implements the Fisher-Yates shuffle. It randomizes arrays.

Shuffle implementation

First, this Shuffle implementation relies on the generic method syntax in the C# programming language. An instance of the Random type is also allocated and stored in a static field. In the Main entry point, we use the Shuffle<T> method on integers and strings; it is equally effective on all types.

Program that implements generic Fischer-Yates shuffle [C#]

using System;

class Program
{
    /// <summary>
    /// Used in Shuffle(T).
    /// </summary>
    static Random _random = new Random();

    /// <summary>
    /// Shuffle the array.
    /// </summary>
    /// <typeparam name="T">Array element type.</typeparam>
    /// <param name="array">Array to shuffle.</param>
    public static void Shuffle<T>(T[] array)
    {
	var random = _random;
	for (int i = array.Length; i > 1; i--)
	{
	    // Pick random element to swap.
	    int j = random.Next(i); // 0 <= j <= i-1
	    // Swap.
	    T tmp = array[j];
	    array[j] = array[i - 1];
	    array[i - 1] = tmp;
	}
    }

    static void Main()
    {
	{
	    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	    Shuffle(array);
	    foreach (int value in array)
	    {
		Console.WriteLine(value);
	    }
	}
	{
	    string[] array = { "dot", "net", "perls" };
	    Shuffle(array);
	    foreach (string value in array)
	    {
		Console.WriteLine(value);
	    }
	}
    }
}

Output

6
8
2
7
4
3
5
9
1
net
perls
dot

Results of the program. The Shuffle<T> method rearranged the nine-element integer array so it is not in its original order. The three-element string array was also rearranged randomly.

Is it correct? Some Shuffle methods have an interesting problem to them: they return incorrect results because they remove elements as they go along. This means that there is a bias to the results; this can be proven through tests.

Alternative implementations

The code in this article is based on the implementation using the Java language found in Wikipedia. I have not tested it exhaustively. The Random type in the .NET Framework uses the same exclusive upper argument to the Next method as does Java to the nextInt method. The generic type in the C# version does not affect the algorithm.

Also, there is a different implementation of Shuffle on this website. The version simply allocates a completely separate list and then assigns every element a random number key; finally, it sorts based on that random number. The linked implementation is very likely much slower in the C# language.

Summary

The Fisher-Yates shuffle algorithm, implemented in 1964 by Durstenfeld and described by Donald Knuth, is an efficient and correct way to sort arrays. This version, which uses the generic method syntax from the C# language and is based on a Java implementation, provides a useful and versatile shuffling routine.