Shuffling randomizes the order of the elements in an array. In my previous post I discussed a method to shuffle an array using sorting technique. Shuffling using sorting is not very efficient due to the presence of nested loop. The complexity is of the order of O(N²) due to the presence of the nested loop in the earlier post. If we use the modern Fisher–Yates algorithm by Richard Durstenfeld the complexity can be reduced to (N). The algorithm is as follows:

To shuffle an array a of n elements (indices 0..n-1):
   for i from n − 1 downto 1 do
      j ← random integer with 0 ≤ j ≤ i
      exchange a[j] and a[i]

The logic is essentially to exchange or swap a random element and keep the exchanged elements towards the end of the list. The shuffling happens in place that is no second array is needed. Also notice that this algorithm requires only one loop due to which performance improves significantly. The Java program to shuffle an array using modern Fisher–Yates algorithm is as follows:

class Fisher_Yates{
     /**
     * shuffle: This function shuffles (disarranges) the argument array using
     *          the modern version of Fisher Yates method by Richard Durstenfeld 
     *          
     *          To shuffle an array a of n elements (indices 0..n-1):
     *          for i from n − 1 downto 1 do
     *             j ← random integer with 0 ≤ j ≤ i
     *             exchange a[j] and a[i]

     * 
     * @param  a   array to be shuffled
     * @return     array containing the shuffled elements 
     */
    public static int[] shuffle(int a[]){
        int j, temp;
        for( int i = a.length -1 ; i >= 1 ;i-- ){
            j = (int)(Math.random() * (i + 1));
            temp = a[ j ];
            a[ j ] = a[ i ];
            a[ i ] = temp;
        }
        return a;
    }
    public static void main(String args[]){
        //declare an array
        int []a={9,8,7,6,5,4,3,2,1};
        //invoke the shuffle method
        a=shuffle(a);
        //display the array via enhanced for construct
        for(int n:a ){
            System.out.println(n);
        }
    }
}

Students are advised to execute the above program to shuffle an array multiple times to verify that it’s giving different output. As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.