Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function random() that generates random number in O(1) time. The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.
Array starts off with 11 elements initialized to array[n] = n, maxIdx starts off at 10:
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
At each iteration, a random number r is selected between 0 and maxIdx, array[randIdx] and array[maxIdx] are swapped, the new array[maxIdx] is returned, and maxIdx is decremented:
maxIdx = 10, randIdx = 3
0
|
1
|
2
|
10
|
4
|
5
|
6
|
7
|
8
|
9
|
3
|
maxIdx = 9, randIdx = 7
0
|
1
|
2
|
10
|
4
|
5
|
6
|
9
|
8
|
7
|
3
|
maxIdx = 8, randIdx = 1
0
|
8
|
2
|
10
|
4
|
5
|
6
|
9
|
1
|
7
|
3
|
maxIdx = 7, randIdx = 5
0
|
8
|
2
|
10
|
4
|
9
|
6
|
5
|
1
|
7
|
3
|
After 11 iterations, all numbers in the array have been selected, maxIdx == 0, and the array elements are shuffled. At this point, maxIdx can be reset to 10 and the process can continue.
Detailed algorithm
To shuffle an array a of n elements (indices 0..n-1):
for i from n - 1 down to 1 do
j = random integer with 0 <= j <= i
exchange a[j] and a[i]
Code to shuffle an array
package com.algorithmforum.rand;
import java.util.Random;
public class RandomGenerator {
/** This function to generate a random permutation of array[]*/
private static void randomize (int array[]) {
int n = array.length;
/*
* Start from the last element and swap one by one.
* We don't need to run for the first element that's why i> 0
*/
for (int i = n-1; i > 0; i--) {
/** Pick a random index from 0 to i.*/
Random rand = new Random();
int value = rand.nextInt(50);
int j = value % (i+1);
/** Swap array[i] with the element at random index. */
swap(i, j, array);
}
}
/** A utility function to swap to integers. **/
private static void swap (int i, int j, int[] array) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/** This is an utility function to print an array. */
private static void printArray (int array[]) {
for (int i:array) {
System.out.print(i+" ");
}
System.out.println();
}
public static void main(String[] args) {
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
randomize(arr);
printArray(arr);
}
}
