Shuffle cards, the dotnet way!!, Is the complexity of algorigthm acceptable?

Question

Using framework's Random class I came up with following lazy implementation to shuffle a deck of card.

I estimate worst case complexity of following code as O(N + NlogN). Am I right?

DataStructures

enum SuitType
{
    Diamond,
    Heart,
    Spade,
    Club
}

class Card
{
    public SuitType suitType;
    public int value;
    public int randomOrder;
}

I have added a variable randomOrder with each card.

Then I am using Randome.Next() to get a random number for each card.

Sort the deck based on this random number.

class Program
    {
        static void Main(string[] args)
        {
            Program p = new Program();

            List<Card> deck = new List<Card>(52);

            p.InitializeDeck(deck);
            List<Card> shuffledDeck = p.ShuffleDeck(deck).ToList();
        }

        Random r = new Random();
        readonly int RMIN = 1, RMAX = 100;

        //O(N + NlogN)
        private  IEnumerable<Card> ShuffleDeck(List<Card> deck)
        {
            //O(N)
            foreach (var d in deck)
            {
                d.randomOrder = r.Next(RMIN, RMAX);
            }
            //O(NlogN)
            return deck.OrderBy(d => d.randomOrder);
        }

        private  void InitializeDeck(List<Card> deck)
        {
            int suitCounter = 0;
            for (int i = 1; i <= 52; i++)
            {
                deck.Add(new Card
                {
                    suitType = (SuitType)suitCounter,
                    value = i,
                    randomOrder = r.Next(RMIN, RMAX)
                });

                if (i % 13 == 0)
                {
                    suitCounter++;
                }
            }
        }
    }

You should check this [question](http://stackoverflow.com/questions/108819/best-way-to-randomize-a-string-array-with-net). — volkh4n, Sep 15 '13 at 12:35
This seems kind of silly when there is a [simple O(n) shuffle algorithm](http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle). — Blastfurnace, Sep 15 '13 at 13:07
[The Danger of Naïveté](http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html). — Hans Passant, Sep 15 '13 at 14:03

score 2 · Answer 1 · edited Jun 20 '20 at 09:12

2

You can replace the whole body of the ShuffleDeck method with

return deck.OrderBy(d => r.Next());

This probably doesn't affect the algorithmic complexity, but it makes the method simpler.

Update:

My opinion is that thinking in terms of Big-O notation is not relevant here unless you have to shuffle millions of decks and discover that performance is really a problem.

edited Jun 20 '20 at 09:12

Community

1
1

answered Sep 15 '13 at 12:27

Cristian Lupascu

39,078
16
100
137

Awesome, in that case I do not even need another variable `randomOrder` in my data structure. – Abhijeet Sep 15 '13 at 12:30
@autrevo yes, `randomOrder` can be removed. IMHO it didn't belong there, anyway. – Cristian Lupascu Sep 15 '13 at 12:33
@autrevo I think your estimation is correct. But please see the update to my answer and see if it makes sense. – Cristian Lupascu Sep 15 '13 at 12:34
1 QQ, how the execution happens at runtime, when we rely on `r.next()` – Abhijeet Sep 18 '13 at 05:51
Does LINQ generates list first & then sorts or it keeps sorting as soon as new random no. is generated from `r.next()`? – Abhijeet Sep 18 '13 at 05:53
@autrevo I just tested and the `r.Next()` is called N times (where N is the size of the deck), just like in your example. Here's the proof: http://ideone.com/inBdQV – Cristian Lupascu Sep 18 '13 at 06:33
@autrevo However, I suggest that you visit the links in the comments to your question. The call to `rand` may be O(n), but the sorting is still O(n log n) and there are better options. – Cristian Lupascu Sep 18 '13 at 06:39

Shuffle cards, the dotnet way!!, Is the complexity of algorigthm acceptable?

1 Answers1

Update: