Hi there,

Here in this blog I am going to provide Java implementation of Fisher-Yates Algorithm for array shuffling. Fisher–Yates shuffle algorithm as named after Ronald Fisher and Frank Yates. It is also known as Knuth shuffle. This algorithm takes O(n) time for shuffling the array. For detailed information you may follow this link http://www.geeksforgeeks.org/shuffle-a-given-array/.

So how Fisher-Yates Algorithm works. Lets suppose we have an array of size n. Now the last element of the array is selected and is swapped with any randomly selected element from the whole array including the last element. Now the last element won't be considered as the part of array for computation purpose, so size of the array is considered as reduced by one i.e. n-1. This given steps will repeat until we left with only one element or we can say until we reached the first element of the array. After this we have an randomly shuffled array.

Java Implementation for the Fisher-Yates algorithm

import java.util.Random;

public class FisherYatesArrayShuffle {

	static void fisherYatesShuffling(int[] a, int n) {
		int tmp;
		int len = n;
		int index;
		Random rand = new Random();

		for (int i = n - 1; i != 0; i--) {
			index = rand.nextInt(len--);
			tmp = a[index];
			a[index] = a[i];
			a[i] = tmp;
		}
	}

	public static void main(String agrs[]) {

		int[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		int n = a.length;
		System.out.print("Input array elements : ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
		fisherYatesShuffling(a, n);
		System.out.print("Output array elements: ");
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}

}

Output of the above program

Input array elements : 0 1 2 3 4 5 6 7 8 9 
Output array elements: 5 3 2 6 9 4 8 1 0 7 

Thanks for reading :)