In this post we will see a few different ways to shuffle arrays, and the advantages and disadvantages of each method. Although the ordering of arrays is a basic part of the syllabus of any introductory computer science course, less attention is paid to the opposite algorithm: how to shuffle an array in a randomised manner.

Shuffle algorithms are used in many areas: cards game where you need to shuffle a deck of cards, puzzles that you need to initialise with a random disposition of the pieces, etc

Think, for example, about a game of cards. A deck with 52 cards: this gives us 52! possible combinations when we shuffle the deck. If our shuffle algorithm is really random any of the 52! possible combinations should be equally probable: if we were to run it repeatedly a high number of times we should not appreciate any of the possible combinations showing up more frequently than the others. Also we should not be able to predict the resulting shuffled deck.

So how can we go about randomly shuffling an array?

Let´s get started with the first and easiest way to shuffle an array: making use of an order by operation:

Random random = new Random();
Enumerable.Range(0, 9).OrderBy(c => random.Next()).ToArray();

In the previous code we generated a list of 0 to 9 numbers, then we assign every and each of them a random number and we order the list by that random number: this process will effectively gets us a shuffled array.

The previous algorithm is quick to implement and easy to understand, but since it has a cost of O(n log n), we could be tempted to look for a more efficient alternative.

Another thing we should consider is how random it is really the resulting shuffled array: the repeated calls to random.Next() could result in various elements of the array having assigned the same number– and that would result in a less randomised result.

We could avoid that pitfall by modifying the previous code like this:

Enumerable.Range(0, 9).OrderBy(c => Guid.NewGuid()).ToArray();

We get ride of the random and we assign every item of the array a GUID – an unique identifier – and we proceed to order the array by that GUID.

Since GUID are unique by definition, now we can be sure that every item of the array has a different value assigned to use in the order by function. But while the GUID are unique is the algorithm used to generate the GUID really random? Well, it turns out that is is not. Raymond Chen summarises it this way in his article: GUIDs are designed to be unique, not random:

The GUID generation algorithm was designed for uniqueness. It was not designed for randomness or for unpredictability.

So let´s try another approach: the Knuth/Fisher-Yates shuffle.

The Fisher-Yates algorithms orders the array in place with a cost of of O(n) following this procedure:

  • Start from the last element
  • Randomly select one element of the array and swap it with the last element
  • Take the array with size decreased in one and repeat the whole process till you reach the first element.

In C# the above algorithm would look like this:

for (int i = inputArray.Length - 1; i > 0; i--)
{
 int randomIndex = random.Next(0, i + 1);

 int temp = inputArray[i];
 inputArray[i] = inputArray[randomIndex];
 inputArray[randomIndex] = temp;
}

Notice that when considering elements in the array for a swap we only consider those elements that had not yet been swapped: this easy to overlook point is a crucial point of the Knuth algorithm. If we ignoring – as The Danger of Naïveté well illustrates – we will be favouring certain sequences over others.

Another interesting article about the Knuth algorithm and the problems associated to its naive/incorrect implementation is How Not To Shuffle – The Knuth Fisher-Yates Algorithm.

I hope you enjoyed this post: if you want to be notified when new articles are added you can click the follow button.