## Wednesday, 4 October 2017

### Algorithms | Shuffle a given array

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);
}
}