Fisher–Yates Shuffle

Fisher–Yates shuffle, also known as Knuth shuffle, is an algorithm for generating a random permutation of a finite set—in plain terms, the algorithm shuffles the set. The algorithm effectively puts all the elements into a hat; it continually determines the next element by randomly drawing an element from the hat until no elements remain.

• C#
• VB.Net
• C
• C++
• PHP

									public static int[] FisherYatesShuffle(int[] data)
{
	int[] retVal = new int[data.Length];
	int[] ind = new int[data.Length];
	int index;
	Random rand = new Random();

	for (int i = 0; i < data.Length; ++i)
		ind[i] = 0;

	for (int i = 0; i < data.Length; ++i)
	{
		do
		{
			index = rand.Next(data.Length);
		} while (ind[index] != 0);

		ind[index] = 1;
		retVal[i] = data[index];
	}

	return retVal;
}
								

Example

									int[] data = { 486, 87, 522, 111, 894, 371, 1, 39 };
int[] retVal = FisherYatesShuffle(data);
								

Output

									retVal: { 371, 486, 39, 894, 111, 522, 87, 1 }