Code shuffle test
I am testing the code I wrote to shuffle the elements of an array. While this is not a real "professional test", I was curious about the results.
I created a random array and kept on shuffling until the array was sorted. I expected the number of times to get the sorted order to be around n! / 2, and the maximum shuffles should be around n !, where n is the number of elements in the array.
With 5 elements, the number of shuffles is roughly 108 and from 6 to 615. I was surprised to see that some of the shuffles took over 500 times even if I only had 5 elements.
My question is, is there an explanation for this result, and / or my arguments for the correct shuffle? My code is in random order
void shuffle(int* array, int length)
{
int i=0;
int r =0;
for(i=0;i<length;i++)
{
r = randomInRange(0,i);
swap(array,i,r);
}
}
source to share
Why n! / 2? The number of permutations is n !, so after n! shuffling, you only expected the numbers to be properly ordered once. The maximum amount of shuffling is with 5 cards, you have a 119/120 chance of getting an unmanageable result at each iteration, and this can go on for a very long time.
Here's the output of a Python script I wrote to count the number of times to correctly guess a random number between 1 and 120:
[17, 43, 251, 72, 4, 10, 41, 61, 74, 22, 172, 49, 43, 66, 994, 99, 59, 88, 255, 48]
The average is 123.4, which is pretty much as expected, but even in this small set of samples, the individual values range from 4 to 994.
However, in your case, the results are slightly different. This is because you are using a shuffle algorithm that gives skewed results. (Jeff Atwood wrote a helpful blog post on the subject.)
I suggest using the Fisher-Yates algorithm instead .
source to share