Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C# Sorting Algorithms
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);
 
                //array = shuffleArray(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
Posted 16-Sep-12 11:11am
sigsand429
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

I think I might have figured out what the problem was.
In my shuffle methods I create a new Random() every time I run it. When I moved that out of the method (just created one Random() object when the program starts) then it seems to work as it should.
Now I get around 100 shuffles until it is sorted with 5 integers which is much closer to what it should be than previously.
Is there someone that knows why this happens? I can't think of why this matters so much.
  Permalink  
Comments
CPallini at 17-Sep-12 8:58am
   
Yes, I observed the same behaviour too. As matter of fact, your (previous) usage of the Random class was plainly wrong. From the Random class documentation (remark section)
"The random number generation starts from a seed value. If the same seed is used repeatedly, the same series of numbers is generated. One way to produce different sequences is to make the seed value time-dependent, thereby producing a different series with each new instance of Random. By default, the parameterless constructor of the Random class uses the system clock to generate its seed value, while its parameterized constructor can take an Int32 value based on the number of ticks in the current time. However, because the clock has finite resolution, using the parameterless constructor to create different Random objects in close succession creates random number generators that produce identical sequences of random numbers. The following example illustrates that two Random objects that are instantiated in close succession generate an identical series of random numbers."
Toli Cuturicu at 17-Sep-12 9:11am
   
My five
CPallini at 17-Sep-12 9:20am
   
Thank you. :-)
sigsand at 17-Sep-12 10:06am
   
Ahhh I see. I thought that since it used the clock as a seed that it would be okay to use it again and again. Somehow I thought the resolution was high enough or this not to happen.
But I am glad that it is solved :D It was making me scratch my head every 5 minutes.
Thanks for the definition.
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

You should definatly read this article:
Visualization and comparison of sorting algorithms in C#[^]
  Permalink  
Comments
sigsand at 17-Sep-12 8:21am
   
Thanks for the link. Does not answer my question though. I was hoping someone might be able to explain why my program behaved so strangely.
I think I might have found out why it does. Will post my solution soon.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Advertise | Privacy | Mobile
Web04 | 2.8.1411022.1 | Last Updated 17 Sep 2012
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100