CSharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript

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.

Based on:.NET 4.5C# program that implements generic Fisher-Yates shuffleusing 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 voidShuffle<T>(T[] array) { int n = array.Length; for (int i = 0; i < n; i++) {// NextDouble returns a random number between 0 and 1. // ... It is equivalent to Math.random() in Java.int r = i + (int)(_random.NextDouble() * (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); foreach (int value in array) { Console.WriteLine(value); } } { string[] array = { "dot", "net", "deves" }; Shuffle(array); foreach (string value in array) { Console.WriteLine(value); } } } }Output6 8 2 7 4 3 5 9 1 net deves 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 randomly rearranged.

**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.

**Princeton:** This code the same as the Java shuffle algorithm from the Princeton computer science introductory course.

**Math.random:** In Java, the Math.random method returns a double between 0 and 1. The NextDouble method in C# is equivalent.

**Note:** Thanks to Darrin Henning for pointing out that the previous algorithm was incorrect.

**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. The implementation may have been wrong.

Fisher-Yates shuffle: Wikipedia

**So:** Currently the method is based on that from a CS textbook used at Princeton University.

**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.

**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.