Shuffling of arrays/lists sounds like a trivial task, but in reality it’s full of subtle traps. Here we show how to implement **Fisher-Yates** **Shuffle Algorithm in Java**.

## Shuffling traps

There are some things to be aware when implementing/choosing **shuffling algorithm**:

- Use good
**Pseudo-Random Number Generator**, one that uniformly distributes random numbers; - Shuffling algorithm should produce
**each permutation with equal probability**; That’s why correct range for random numbers is important. Taking wrong range may produce biased results, which is illustrated nicely at Data Genetics (see the Monte Carlo simulation at the bottom).

## Fisher-Yates shuffle

The most known and optimal shuffling algorithm is Fisher-Yates shuffle. The algorithm is very easy to implement and produces **unbiased results**. It has been modernized by **Durstenfeld** and popularized by **Donald Knuth** in **The Art of Computer Programming** TV series. The Durstenfeld’s implementation of the **Fisher-Yates shuffling algorithm** is extremely simple and boils down to just a few lines of code. What’s important, it runs in **linear time** and works **in place**:

// T[] data, Random rand for (int i = data.length-1; i > 0; --i) { swap(data, i, rand.nextInt(i+1)); }

### How Durstenfeld shuffling works

- Go from the end of the array/list (you can process in the oposite direction by just changing directions in all the steps).
- Pick random number between 0 and the current position (both inclusive).
- Exchange the current item with the random one.

## Complete Java example

package com.farenda.tutorials.algorithms.shuffling; import java.util.Arrays; import java.util.Random; public class RandomSort { public static void main(String[] args) { String[] data = "HelloShuffleWorld!".split(""); System.out.println("Before shuffle: " + Arrays.toString(data)); shuffle(data, new Random()); System.out.println("Shuffled: " + Arrays.toString(data)); } private static <T> void shuffle(T[] data, Random rand) { for (int i = data.length-1; i > 0; --i) { swap(data, i, rand.nextInt(i+1)); } } private static <T> void swap(T[] data, int i, int j) { T tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }

If you happen to know why there is no **swap()** method in **java.util.Arrays**, please let me know in the comments! This is just incredible.

The above code produces shuffled output:

Before shuffle: [H, e, l, l, o, S, h, u, f, f, l, e, W, o, r, l, d, !] Shuffled: [r, W, l, l, h, o, f, d, e, l, e, f, H, o, !, u, S, l]

Now you are ready to implement **card shuffling** in you games. :-)

## References:

- Fisher-Yates shuffle in Wikipedia
- Biased and unbiased shuffling visualization at DataGenetics
- How to use Collections.shuffle(List) from JDK to shuffle a List
- Shuffling in fantastic
**Algorithms and Data Structures**course