Shuffle

We can develop a Java shuffling algorithm. In shuffling, we take a sorted array and mess it all up. We rearrange elements randomly, like a deck of cards.

In Fisher-Yates shuffle, a fast shuffling algorithm, we loop over an array. We swap each element with a random element past the iteration point.

In this program, we implement the shuffling algorithm. We call the Math.random() method, which returns a random double between 0 and 1. We use this to select a random index.

Then We swap the randomly selected "forward" element with the current element.

Result The input array (in this code, an int array) is now randomly sorted. Like a deck of cards, it is shuffled.

Important We should use nextInt instead a multiplication with Math.Random to avoid bias in the results.

public class Program {

    static void shuffle(int[] array) {
        int n = array.length;
        Random random = new Random();
        // Loop over array.
        for (int i = 0; i < array.length; i++) {
            // Get a random index of the array past the current index.
            // ... The argument is an exclusive bound.
            //     It will not go past the array send.
            int randomValue = i + random.nextInt(n - i);
            // Swap the random element with the present element.
            int randomElement = array[randomValue];
            array[randomValue] = array[i];
            array[i] = randomElement;
        }
    }

    public static void main(String[] args) {

        int[] values = { 100, 200, 10, 20, 30, 1, 2, 3 };
        // Shuffle integer array.
        shuffle(values);

        // Display elements in array.
        for (int value : values) {
            System.out.println(value);
        }
    }
}10
100
1
200
3
20
2
30

`Collections.shuffle`

The Collections class in java.util.Collections provides a shuffle() method. This receives an argument like an ArrayList.

Here We call Collections.shuffle multiple times on an ArrayList. Its ordering changes after each call.

import java.util.ArrayList;
import java.util.Collections;

public class Program {

    public static void main(String[] args) {

        // Create an ArrayList of 4 elements.
        ArrayList<Integer> array = new ArrayList<>();
        array.add(1);
        array.add(2);
        array.add(3);
        array.add(4);
        System.out.println("BEFORE: " + array.toString());

        // Shuffle elements.
        Collections.shuffle(array);
        System.out.println("AFTER 1: " + array.toString());

        // Shuffle elements again.
        Collections.shuffle(array);
        System.out.println("AFTER 2: " + array.toString());
    }
}BEFORE: [1, 2, 3, 4]
AFTER 1: [3, 2, 4, 1]
AFTER 2: [4, 1, 3, 2]

Alternative

Here is another strategy: we can generate an array of random numbers that is the same length as our array. Then we sort both arrays together.

And This will randomly sort (or shuffle) the array, provided our random number generator is random enough.

However This is not fast. But if your program only shuffles occasionally, this may be fast enough.

Correctness is key

With Fisher-Yates shuffling, we have a fast and useful algorithm. But implementing the indexes (and the index section part) is prone to small errors in logic.