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.