In some applications like card games, we need to shuffle an array of objects. In this post we will consider the problem of shuffling an array of numbers so that the same algorithm would be applicable for any type of arrays.
We use the random number generator in this algorithm. Let us consider an array of n numbers. It’s element are in the range of 0 to n-1 indices. We first select a random number between 0 to n-1 indices,and swap the random element with the last element. In the next iteration, we exclude the last element (thus reducing the array size by 1) and repeat the same procedure.
Here is the Java code which implements this approach.
import java.util.Random;
/**
*
* @author Ravi
*/
public class ShuffleArray {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
int [] array = new int[10];
int i;
//fill the array with numbers 1-100
for( i = 0 ; i < 10 ; i++)
{
array[i] = i+1;
}
//call shuflle array method
shuffleArray(array);
//print the shuffled array
for( i = 0 ; i < 10 ; i++)
{
System.out.print(array[i]+" ");
}
}
public static void shuffleArray(int[] array)
{
int i;
//random number generator
Random rd = new Random();
//start from the end
for( i = array.length-1 ; i > 0 ; i--)
{
//generates a random number between [0,i] inclusive
int randomIndex = rd.nextInt(i+1);
//swap the element at random index with ith element
int temp = array[randomIndex];
array[randomIndex] = array[i];
array[i] = temp;
}
}
}