Shuffle List<T> [duplicate]

Question

Possible Duplicate:
Randomize a List<T> in C#

I have a list which contains many thousands of FilePath's to locations of audio files, and was wondering which would be the most efficient way to "shuffle" a List?

Any help is greatly appreciated :)

Thank you

Answer 1

Fisher-Yates Shuffle or as it is also known as, Knuth shuffle.

Answer 2

Here is a simple (yet effective) implementation of the Fischer-Yates/Knuth shuffle:

Random rnd = new Random();
for (int i = files.Length; i > 1; i--) {
  int pos = rnd.Next(i);
  var x = files[i - 1];
  files[i - 1] = files[pos];
  files[pos] = x;
}

Or a slight variation:

Random rnd = new Random();
for (int i = 1; i < files.Length; i++) {
  int pos = rnd.Next(i + 1);
  var x = files[i];
  files[i] = files[pos];
  files[pos] = x;
}

As this is an O(n) operation, it's the most efficient way of shuffling a list. As all items in the list has to have chance to be moved, it's not possible to shuffle a list more efficiently than O(n).

I made a small performance test by shuffling a million items a thousand times each using this method and the currently accepted answer (LINQ OrderBy), and this is about 15 times (!) faster.

Answer 3

myList.OrderBy(Guid.NewGuid())

Answer 4

I added Jon Skeet's solution from this question to my Extensions library. I implemented methods that both take an external random number generator and create one using a default implementation (Random).