Monday, June 3, 2013

Program to shuffle an array

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