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.



									/*****Please include following header files*****/
// stdlib.h
/***********************************************/

int* FisherYatesShuffle(int* data, int count)
{
	int* retVal = (int*)malloc(sizeof(int) * count);
	int* ind = (int*)malloc(sizeof(int) * count);
	int index;

	for (int i = 0; i < count; ++i)
		ind[i] = 0;

	for (int i = 0; i < count; ++i)
	{
		do
		{
			index = rand() % count;
		} 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, 8);
								


Output

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