C# Fisher-Yates Shuffle

Algorithm: shuffle elements

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

Example

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.

Static MethodGeneric MethodRandomStatic Field

Next: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
Array type

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 randomly rearranged.

Int Array

Is it correct? Some Shuffle methods have an interesting problem. 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.

Discussion

Framework: NET

This code is based on the implementation using the Java language found in Wikipedia. I have not exhaustively tested it. The Random type uses the same exclusive upper argument to the Next method as does Java to the nextInt method.

Fisher-Yates shuffle: WikipediaProgramming tip

Also, there is a different implementation of Shuffle on this website. The version simply allocates a separate list and then assigns every element a random number key. It sorts based on that random number.

Caution:The linked implementation is likely much slower than Fisher-Yates in the C# language.

Shuffle Array

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. It provides a useful, versatile shuffling routine.


C#: Method