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

29 Mar 08 | Programming

16 Responses to “Shuffle a Collection”

Carlos Rodrigues | March 29th, 2008 at 1:28 pm

That looks both wrong and inefficient. First, the result of the comparison between two different elements is random, which can have unexpected interactions with the sorting algorithm underneath. Second, you are generating a random number for every comparison… And third, this can never be proven to be unbiased…

A real unbiased shuffle either uses something like the Fisher-Yates algorithm or you associate a random number for every element in the list and then sort by than number.
Nuno Silva | March 29th, 2008 at 1:51 pm

Actually you’re right. I tought the was the comparer was more optimized.

So i did a test:

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

There is a realy big diference. Thanks for the remark
Jos Hirth | March 29th, 2008 at 8:51 pm

I came up with a very nice (continuous) shuffling algorithm:

http://kaioa.com/node/53

The shuffling overhead is spread across the draws, it does as little as possible, and it’s also very easy to port. It’s pretty much the ultimate solution to this problem.
Carlos Rodrigues | March 30th, 2008 at 4:29 pm

You can try another benchmark, shuffle a simple “abc” array with both methods a couple thousand times, and compare their statistical distributions.
Nuno Silva | March 30th, 2008 at 10:04 pm

Hi Jos. Thanks for the link. Interesting solution.

Carlos, i will do that just to see the diference between them
Glen Hollie | December 24th, 2009 at 2:32 am

Kicking off 2010’s mma events is the amazing UFC 108. It’s definitely going to be a great event with the kickoff being Evans vs Silva going head to head. You can watch ufc 108 live for FREE in full HD without paying that grotty $55.95 PPV cost.
Lorenzo Times | January 28th, 2010 at 11:34 pm

Outstanding read, I just passed this onto a fellow worker who was doing a small research on that. And he actually purchased me lunch cause I found it for him.
Alma Daber | February 3rd, 2010 at 12:35 am

Hey awesome blog, just want to ask you what spam system you use for comments since I get tons on my website.
zynga chips | March 20th, 2010 at 7:27 pm

i probably would not have thought this was useful many years ago then again it is crazy the way time evolves the manner by which you respond to new kinds of ideas, many thanks regarding the post it happens to be relaxing to start reading anything intelligent now and then instead of the ordinary crap mascarading as information sites on the net, i’m going to enjoy a smattering of rounds of facebook poker, adios for now
Chi Sa | March 30th, 2010 at 12:05 am

check out http://ppvevents.net for all free ppv sport events
how to lose weight in a week | June 6th, 2010 at 12:23 am

lose weight in a week
Jake Piacente | September 22nd, 2010 at 2:47 pm

Sick and tired of obtaining low numbers of useless visitors to your site? Well i wish to let you know about a new underground tactic that produces me personally $900 per day on 100% AUTOPILOT. I could be here all day and going into detail but why dont you merely check their website out? There is really a excellent video that explains everything. So if your serious about making hassle-free money this is the website for you. Auto Traffic Avalanche
Remedios Lanosa | December 11th, 2011 at 5:35 am

A lot of thanks for all of the work on this web page. Gloria really likes conducting internet research and it is obvious why. A lot of people know all concerning the lively way you offer important tactics by means of this blog and even strongly encourage response from some others on that area plus our own daughter is really understanding a lot of things. Enjoy the remaining portion of the year. You’re the one performing a dazzling job.
Mozelle Mchan | December 11th, 2011 at 11:33 pm

I like your article very much you have given a good massage for all.This is very exciting that how to make money on eBoy.
click | May 30th, 2012 at 10:04 pm

The structure for your website is a bit off in Epiphany. Nevertheless I like your web site. I may need to install a normal web browser just to enjoy it.
travel tour services | May 27th, 2013 at 1:50 pm

I’ll right away clutch your rss feed as I can not in finding your e-mail subscription hyperlink or newsletter service. Do you’ve any? Kindly let me recognize so that I may subscribe. Thanks.

The Guy

My name is Nuno Silva and I am the author of this blog. I am a Computer Engineer and have a passion for game development.

So, in this blog you find especially things about the web, game development, software, my personal projects (Orion's belt for instance) and, sometimes, just crazy things that pass through my head.