Most efficient way to randomly "sort" (Shuffle) a list of integers in C#

Question

I need to randomly 'sort' a list of integers (0-1999) in the most efficient way possible. Any ideas?

Currently, I am doing something like this:

bool[] bIndexSet = new bool[iItemCount];

for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++)
{
    int iSwapIndex = random.Next(iItemCount);
    if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex)
    {
        int iTemp = values[iSwapIndex];
        values[iSwapIndex] = values[iCurIndex];
        values[iCurIndex] = values[iSwapIndex];
        bIndexSet[iCurIndex] = true;
        bIndexSet[iSwapIndex] = true;
    }
}

Answer 1

A good linear-time shuffling algorithm is the Fisher-Yates shuffle.

One problem you'll find with your proposed algorithm is that as you near the end of the shuffle, your loop will spend a lot of time looking for randomly chosen elements that have not yet been swapped. This may take an indeterminate amount of time once it gets to the last element to swap.

Also, it looks like your algorithm will never terminate if there are an odd number of elements to sort.

Answer 2

To improve your efficiency you can keep a set of values/indices that have been swapped rather than a boolean for indicating they were swapped. Pick your randomized swap index from the remaining pool. When the pool is 0, or when you made it through the initial list then you are done. You don't have the potential to try to select a random swap index value.

When you do a swap, just remove them from the pool.

For the size of data you are looking at it is no big deal.

Answer 3

I am not sure of the efficiency factor, but I have used something similar to the following, if you aren't opposed to using an ArrayList:

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }

    return sortedList;
}

Using this, you do not have to worry about the intermediate swapping.

Answer 4

As Greg pointed out the Fisher-Yates shuffle would be the best approach. Here is an implementation of the algorithm from Wikipedia:

public static void shuffle (int[] array)
{
   Random rng = new Random();   // i.e., java.util.Random.
   int n = array.length;        // The number of items left to shuffle (loop invariant).
   while (n > 1)
   {
      int k = rng.nextInt(n);  // 0 <= k < n.
      n--;                     // n is now the last pertinent index;
      int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
      array[k] = temp;
      array[n] = array[k];
   }
}

The implementation above relies on Random.nextInt(int) providing sufficiently random and unbiased results

Answer 5

Wouldn't something like this work?

var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
var random = new Random();
list.Sort((a,b)=>random.Next(-1,1));

Answer 6

A generic implimentation of the Fisher-Yates shuffle:

public static T[] RandomPermutation<T>(T[] array)
{
    T[] retArray = new T[array.Length];
    array.CopyTo(retArray, 0);

    Random random = new Random();
    for (int i = 0; i < array.Length; i += 1)
    {
        int swapIndex = random.Next(i, array.Length);
        if (swapIndex != i)
        {
            T temp = retArray[i];
            retArray[i] = retArray[swapIndex];
            retArray[swapIndex] = temp;
        }
    }

    return retArray;
}

I have made it return a new array as I don't much like the idea of modifying the in paramater, but you can change it to do that if you want.

Answer 7

We can make an extension method out of this to get a Random enumerator for any IList collection

class Program
{
    static void Main(string[] args)
    {
        IList<int> l = new List<int>();
        l.Add(7);
        l.Add(11);
        l.Add(13);
        l.Add(17);

        foreach (var i in l.AsRandom())
            Console.WriteLine(i);

        Console.ReadLine();
    }
}


public static class MyExtensions
{
    public static IEnumerable<T> AsRandom<T>(this IList<T> list)
    {
        int[] indexes = Enumerable.Range(0, list.Count).ToArray();
        Random generator = new Random();

        for (int i = 0; i < list.Count; ++i )
        {
            int position = generator.Next(i, list.Count);

            yield return list[indexes[position]];

            indexes[position] = indexes[i];
        }
    }
}

This uses a reverse Fisher-Yates shuffle on the indexes of the list we want to randomly enumerate through. Its a bit of a size hog (allocating 4*list.Count bytes), but runs in O(n).

Answer 8

I like your answer Micah, but you need to swap the 2nd and 3rd lines in your swap, so it reads:

int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
array[n] = array[k];
array[k] = temp;

Answer 9

I made a method using a temporary Hashtable, allowing the Hashtable's natural key sort to randomize. Simply add, read and discard.

int min = 1;
int max = 100;
Random random;
Hashtable hash = new Hashtable();
for (int x = min; x <= max; x++)
{
    random = new Random(DateTime.Now.Millisecond + x);
    hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x);
}
foreach (int key in hash.Keys)
{
    HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key);
}
hash.Clear(); // cleanup

Answer 10

I guess the last two lines must be interchanged in Micah's answer. So, the code might look like

 public static void shuffle(int[] array) {
        Random rng = new Random();   // i.e., java.util.Random.
        int n = array.Length;        // The number of items left to shuffle (loop invariant).
        while (n > 1) {
            int k = rng.Next(n);  // 0 <= k < n.
            n--;                     // n is now the last pertinent index;
            int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
            array[n] = array[k];
            array[k] = temp;

        }
    }