usually, most of the manipulations that are being done with lists are sorting. therefore most of the .Net Framework solutions are for doing that. But what if we want to shuffle a list instead of sorting it?
well, I have bump into that problem while ago, and try to come up with the most elegant solution for doing it.
my first approach was using the existing .Net Framework solutions for sorting and manipulate them in a way to provide a shuffling solution.
so I did as follow:
I have created a RandomComparer who implements IComparer<int> with the following compare method:
public int Compare(int x, int y)
{
if (x == y) return 0;
else return random.Next(2) == 0 ? 1 : -1;
}
Then, I shuffled the list while using the RandomComparer I have created:
List<int> sortedList = GetSortedList();
List<int> shuffledList;
shuffledList = sortedList.Sort(RandomComparer.Instance);
Looks like an elegant solution? well, it has 2 problems:
- performance - sorting a list takes in the worst case O(n lgn) while shuffling can take O(n)
- after running this code in load test I have noticed that once in ~200 times, a System.ArgumentException is being thrown saying: “IComparer did not return zero when Array.Sort called x. CompareTo(x). x”.
notice that the Compare method described above returns 0
if(x == y). after investigating this I figure that in some cases there is 3 parameters comparison, and some times we get:
a > b, b > c, c> a. which makes no sense…
So, the best way I come up with is a simple implementation of a shuffle method that picks a random value from the sorted list and add it to the shuffled list:
public List<int> Shuffle(List<int> sortedList)
{
List<int> shuffledList = new List<int>(sortedList.Count);
int count = sortedList.Count;
for (int i = 0; i < count; i++)
{
int j = random.Next(sortedList.Count);
shuffledList.Add(sortedList[j]);
sortedList.Remove(sortedList[j]);
}
return shuffledList;
}
notice that this solution takes in the worst case O(n)
