Hi.
I am writing a small program that will plot the running times of some algorithms. I am writing some methods that shuffle a deck of cards (just 52 integers in an int array).
Here are my methods:
// Creates a sorted int array.
private int[] createNonRandomArray(int size, int startingNumber)
{
int[] array = new int[size];
for (int i = 0; i < size; i++)
{
array[i] = startingNumber;
startingNumber++;
}
return array;
}
// Shuffles array using Fisher Yates algorithm.
private int[] fisherYatesShuffle(int[] array)
{
Random rnd = new Random();
for (int i = array.Length - 1; i >= 0; i--)
{
int r = rnd.Next(0, i + 1);
int tmp = array[i];
array[i] = array[r];
array[r] = tmp;
}
return array;
}
// Checks if an int array is sorted.
private bool isInOrder(int[] array)
{
int referance = 0;
foreach (int i in array)
{
if (!(i > referance))
{
return false;
}
referance = i;
}
return true;
}
Now I implemented code that simply shuffles the deck and checks if it is sorted, if it is not then repeat until it is sorted. Here is that code:
private void backgroundWorkerAlgorithm_DoWork(object sender, DoWorkEventArgs e)
{
int[] array = createNonRandomArray(5,1);
int y = 0;
foreach (int i in array)
{
Console.WriteLine(i);
}
array = fisherYatesShuffle(array);
foreach (int i in array)
{
Console.WriteLine(i);
}
int numberofruns = 0;
Stopwatch sw = new Stopwatch();
sw.Start();
while (true)
{
array = fisherYatesShuffle(array);
if (isInOrder(array))
{
break;
}
if (numberofruns % 10 == 0)
{
Console.WriteLine(numberofruns);
}
numberofruns++;
}
sw.Stop();
Console.WriteLine("Time it took: " + sw.ElapsedMilliseconds+" -- "+sw.Elapsed);
Console.WriteLine("Number of runs: " + numberofruns);
}
Now if I am not mistaken then a "deck" with five cards has 5! (120) possible ways of being arranged. So it should take somewhere around that many times on average to "sort" the deck using this method.
My code usually gives me a sorted deck in 4 "numberofruns" and sometimes, but rarely, it takes thousands of "numberofruns".
Can someone point out what I am doing wrong?
Typical output of my program:
1
2
3
4
5
4
1
5
3
2
0
Time it took: 0 -- 00:00:00.0000143
Number of runs: 3