Test for shuffling code

Question

I am testing some code I wrote to shuffle elements of an array. While not a real "professional test", I was wondering about the results.
I generated a random array and kept shuffling it until the array is sorted. I expected the number of times to get the sorted order, to be around n!/2 and maximum shuffles needed to be around n!, where n is the number of elements in the array.

With 5 elements, number of shuffles averages to around 108 and with 6 to around 615. I was surprised to see that certain shuffles took more that 500 times even if I had only 5 elements.

My question is that, is there a explanation for this result, and/or is my reasoning for the expected shuffles correct? My shuffle code

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);
    }
}

Answer 1

Why n!/2? The number of permutations is n!, so after n! shuffles you would only expect to have the numbers correctly ordered once. There is no maximum number of shuffles — with 5 cards, you have a 119/120 chance of getting a non-ordered result at each iteration, and this could go on for a very long time.

Here's the output of a Python script I wrote to count the number of times it took to correctly guess a random number from 1 to 120:

[17, 43, 251, 72, 4, 10, 41, 61, 74, 22, 172, 49, 43, 66, 994, 99, 59, 88, 255, 48]

The average value is 123.4, which is pretty much as expected, but even in this small sample set, the individual values range from 4 to 994.

However, in your case, the results are slightly different. This is because you're using a shuffling algorithm that gives skewed results. (Jeff Atwood has written a useful blog post on the subject.)

I suggest you use the Fisher-Yates algorithm instead.