Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Shuffle Algorithm in Java

farenda 2017-04-22 0

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

  1. Go from the end of the array/list (you can process in the oposite direction by just changing directions in all the steps).
  2. Pick random number between 0 and the current position (both inclusive).
  3. 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
Share with the World!
Categories Algorithms Tags algorithms, java, shuffling
Previous: MD5 hash in Java
Next: Palindrome detector in Java

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2022

sponsored
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok