Fisher-Yates shuffle. 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. Not only this, but this implementation of Shuffle() is fast and does not require any allocation.
This Shuffle implementation relies on the generic method syntax in the C# language. An instance of the Random type is also allocated and stored in a static field.
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>
static void Shuffle<T>(T[] array)
{
int n = array.Length;
for (int i = 0; i < (n - 1); i++)
{
// Use Next on random instance with an argument.// ... The argument is an exclusive bound.// So we will not go past the end of the array.
int r = i + _random.Next(n - i);
T t = array[r];
array[r] = array[i];
array[i] = t;
}
}
static void Main()
{
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Shuffle(array);
Console.WriteLine("SHUFFLE: {0}", string.Join(",", array));
string[] array2 = { "bird", "frog", "cat" };
Shuffle(array2);
Console.WriteLine("SHUFFLE: {0}", string.Join(",", array2));
}
}SHUFFLE: 3,5,7,8,6,9,1,2,4
SHUFFLE: cat,frog,bird
Some Shuffle methods have serious problems. They return incorrect results because they remove elements as they go along. There is a bias to the results.
Detail This code the same as the Java shuffle algorithm from the Princeton computer science introductory course.
Detail In Java, the Math.random method returns a double between 0 and 1. The NextDouble method in C# is equivalent.
A discussion. Shuffle algorithms are hard to develop and test. Often biases can occur. Previously, I had based this code on a Java implementation from Wikipedia, but this was removed.
So The implementation may have been wrong. Currently the method is based on code from a CS textbook used at Princeton University.
A 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. The implementation here has been tested and analyzed to ensure it is relatively free of problems.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Apr 27, 2023 (edit).
