Support free tutorials:











vogella training Training Books



Shuffle an Array or a List - Algorithm in Java - Tutorial

Lars Vogel

Version 0.1

17.05.2009

Revision History
Revision 0.1 17.05.2009 Lars
Vogel
Created

Abstract

This article describes how to shuffle the content of an array or a list in Java. After the shuffle the elements in the array or the list are randomly sorted.


Table of Contents

1. Shuffle an array with the Collections framework
2. Implementation in Java
3. Support this website
3.1. Thank you
3.2. Questions and Discussion
4. Links and Literature
4.1. Source Code
4.2. General

1. Shuffle an array with the Collections framework

An array or an java.util.list contains a sorted list of values. Shuffling an array or a list means that you are randomly re-arranging the content of that structure. Have you wondered how you could shuffle an array or a list without the collection framework? This article demonstrates how the shuffling works so that you can learn how the standard libraries might do this.

Tip

If you only interested in shuffling with the collections framework you should of course use the standard Java. Use Collections.shuffle(list) to shuffle a list with the standard Java library or Collections.shuffle(Arrays.asList(a)) to shuffle an array a.

The approach works independent of the content of the array or the list.

The shuffle is random as the algorithm by selecting uniformly en element which has not been selected. For example if the element at position 2 is selected it can be exchanged with all elements at position 2 until position n-1 (as the list /array has 0 - n-1 positions).

2. Implementation in Java

Create a Java project "de.vogella.algorithms.shuffle".

Create the following program for sorting arrays.

package de.vogella.algorithms.shuffle;

import java.util.Random;

public class ShuffleArray {
  public static void shuffleArray(int[] a) {
    int n = a.length;
    Random random = new Random();
    random.nextInt();
    for (int i = 0; i < n; i++) {
      int change = i + random.nextInt(n - i);
      swap(a, i, change);
    }
  }

  private static void swap(int[] a, int i, int change) {
    int helper = a[i];
    a[i] = a[change];
    a[change] = helper;
  }

  public static void main(String[] args) {
    int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7 };
    shuffleArray(a);
    for (int i : a) {
      System.out.println(i);
    }
  }
} 

Create the following program for sorting list.

package de.vogella.algorithms.shuffle;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ShuffleList {
  public static void shuffleList(List<Integer> a) {
    int n = a.size();
    Random random = new Random();
    random.nextInt();
    for (int i = 0; i < n; i++) {
      int change = i + random.nextInt(n - i);
      swap(a, i, change);
    }
  }

  private static void swap(List<Integer> a, int i, int change) {
    int helper = a.get(i);
    a.set(i, a.get(change));
    a.set(change, helper);
  }

  public static void main(String[] args) {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    shuffleList(list);
    for (int i : list) {
      System.out.println(i);
    }
  }
} 

Why does this shuffle all values randomly? The value at position 0 is exchanged with a randomly selected value (including the original value at position 0). This means that after the first loop position 0 has a random value with an equal likelihood of any value. We continue this with position 1 but we do not need to consider position 0 again as this position already has a random value assigned. After the loop it is equally likely that any value is at any position.

3. Support this website

This tutorial is Open Content under the CC BY-NC-SA 3.0 DE license. Source code in this tutorial is distributed under the Eclipse Public License. See the vogella License page for details on the terms of reuse.

Writing and updating these tutorials is a lot of work. If this free community service was helpful, you can support the cause by giving a tip as well as reporting typos and factual errors.

3.1. Thank you

Please consider a contribution if this article helped you.

Flattr this

3.2. Questions and Discussion

If you find errors in this tutorial, please notify me (see the top of the page). Please note that due to the high volume of feedback I receive, I cannot answer questions to your implementation. Ensure you have read the vogella FAQ as I don't respond to questions already answered there.

4. Links and Literature

4.1. Source Code

Source Code of Examples

4.2. General

Not listed yet