Nuno Silva

Shuffle a Collection

Shuffle a collection… hum, i must iterate the collection, change the elements from place, bummer… Well, not really.

The only thing you need to do to shuffle a collection is……. a sort.

Explaining: In C#, a Collection like List<t> (where T is the template element) has a method named Sort. Well, this method can receive has a parameter an IComparer<t>, an object that compares 2 other objects of type T.

The object that implement IComparer should look like this:

public class ElementShuffle : IComparer<element> {

	#region Fields

	Random rnd = new Random()

	#region 

	#region IComparer<element> Members

	public int Compare( Element x, Element y ) {
 		if( x.Equals(y)) {
 			return 0;
 		}
	 	return rnd.Next(-1, 1);
 	}

	#endregion

}

In the above class, Element is the type of object of the collection, and ElementShuffle the implementation of IComparer<T>.

When you want to shuffle you collection you just need to call the Sort method:

List<Element> elements = new List<Element>();
...
elements.Sort(new ElementShuffle());

So what you gain by doing this? A much cleaner code, and a very easy way to do a shuffle.

But not the most efficient. Although it’s a clean way to make, like Carlos Rodrigues said in his comment to this post, this way may not be the most efficient. The Fisher-Yates algorithm:

	public static void Shuffle( List elements ) {
		Random rng = new Random();
		int n = elements.Count;
		while( n > 1 ) {
			int k = rng.Next(n);
			–n;
			int temp = elements[n];
			elements[n] = elements[k];
			elements[k] = temp;
		}
	}

Source: Fisher-Yates algorithm - Wikipedia

Is a lot faster. Here are the results:

Time Fisher-Yates algorithm: 220,3168 ms
Time Comparer: 2213,1824 ms

With this post i learned a lesson: Sometimes the most elegant way to resolve a problem, is not the most efficient. It’s always good to check if your algorithm is more or less efficient than a “not so elegant way”.

Random Posts

• Parkour
• I want one of these without reflection, please!
• Wherigo: An interesting concept
• Orion’s Belt Development Blog
• 50 games in one Semester?