I recently developed a self-sorted IList implementation for a project and I needed some automated way to unit test it - so naturally, the best way to automatically test a sorting function is to force it to sort the results of an unsorting function ;). Just for reference, IList is the interface implemented by every sort of List<T> variant in the .NET Collections library, with the notable exception of SortedList which is really a misnomer given that it actually implements IDictionary instead of IList.

I was excited at the prospect of developing my own unsorting method, but sadly a quick Bing query revealed a couple of solutions developed by programmers far more diligent than I, and I decided to roll both of their solutions into a pair of generic extension methods which I have tested and built into my solution. Let's take a look at them:

Solution 1 - Randomizing an IList<T> Object Using LINQ Projection

By far the most simple, yet elegant method for randomizing the contents of an IList object I found was this one developed by Sven Groot, which uses LINQ's OrderBy method to randomize the contents of an IEnumerable object:

public static IEnumerable<T> Randomize<T>(this IEnumerable<T> source)
{
    Random rnd = new Random();
    return source.OrderBy<T, int>((item) => rnd.Next());
}

In terms of brevity, it doesn't get much better than this. Also, given that I need to ultimately create an IList<T> object out of this randomized collection remember that List<T> has a constructor which accepts an IEnumerable<T> collection as an argument.

Solution 2 - Randomizing an IList<T> Object Using an Index Swap Routine

The more traditional, pre-LINQ solution would be to randomize the contents of an IList<T> object using a swap routine given that all IList objects have indexers, which is exactly what Jon Skeet did using this solution:

Random rng = new Random();
for (int i = list.Count - 1; i > 0; i--)
{
    int swapIndex = rng.Next(i + 1);
    if (swapIndex != i)
    {
        //Changed this from "object" to "T" in order to support generics.
        object tmp = list[swapIndex];
        list[swapIndex] = list[i];
        list[i] = tmp;
    }
}

If you have time, make sure you read Jon's explanation of how the algorithm works (it's pretty cool imho.) I went ahead and wrapped this code into an extension method just like Sven's LINQ solution, and here's what that looks like:

public static IEnumerable<T> RandomizeWithSwaps<T>(this IList<T> list)
{
    Random rng = new Random();
    for (int i = list.Count - 1; i > 0; i--)
    {
        int swapIndex = rng.Next(i + 1);
        if (swapIndex != i)
        {
            //Changed this from "object" to "T" in order to support generics.
            T tmp = list[swapIndex];
            list[swapIndex] = list[i];
            list[i] = tmp;
        }
    }

    return list;
}

One thing worth noting is that this extension method will only work with IList types - IEnumerable doesn't have any support for indexers, thus this extension method is somewhat wonky. Given that, I went with using the LINQ solution in my unit testing code.

If you enjoyed this post, make sure you subscribe to my RSS feed!