Tag Archives: sorting

Shuffle an array

Shuffling randomizes the order of the elements in an array. In this post I will be discussing a very simple method of shuffling an array suitable for students of ICSE and ISC. The current discussion would concentrate more on getting the job done than efficiency. I will be writing a follow-up post in which I will discuss a more efficient approach to shuffle an array.

Shuffling an array means in very simple term that we are interested in disarranging the array. Shuffle an array problem seems to be reverse of sorting but the method which we would be using in this post would be sorting with a twist!

In order to shuffle an array we would be taking another float array whose size would be same as that of the array we want to shuffle. I would be referring to this other array by the name dummy array in this post. We will initialize this array with random values. The method random of Math class would be used to initialize the dummy array with random values.  The random method returns a double value with a positive sign, greater than or equal to 0.0 and less than 1.0. Returned values are chosen pseudorandomly with (approximately) uniform distribution from that range. Since we don’t need a lot of precision we would typecast this double value into a float. The dummy array initialized with random values would then be sorted in ascending order using bubble sort. Please note that the order of sorting that is ascending or descending and the method of sorting is not relevant. The dummy array may be sorted using either ascending or descending order using any method with which the student is comfortable with. The important aspect of sorting in this case is to swap the elements of the original array positions also when the elements of the dummy array are being swapped. This would lead to disarrangement of the original elements as the dummy elements are being sorted. The Java program to shuffle an array using the method discussed above is as follows:

class Shuffle{
     /**
     * shuffle: This function shuffles (disarranges) the argument array
     * 
     * @param  a   array to be shuffled
     * @return     array containing the shuffled elements 
     */
    public static int[] shuffle(int a[]){
        // create a float array of the same size as the argument array
        float []dummy = new float [a.length];
        //initializing dummy array with random
        //values
        for( int i = 0; i < a.length ; i++ ){
            dummy[i] = (float)Math.random();
        }
        //temporary variable for swapping
        int temp1;
        float temp2;
        //sorting the dummy array initialized with random values
        //using bubble sort
        for( int i=0 ; i < a.length-1 ; i++ ){
            for( int x=0; x< a.length-i-1 ; x++ ){
                if( dummy[ x+1 ] < dummy[ x ] ){
                    //swapping dummy positions for dummy array
                    temp2 = dummy[ x+1 ];
                    dummy[ x+1 ] = dummy[ x ];
                    dummy[ x ] = temp2;

                    //swapping positions of the array to be shuffles
                    //whenever the positions of dummy is being swapped
                    temp1 = a[ x+1 ];
                    a[ x+1 ] = a[ x ];
                    a[ x ] = temp1;
                }
            }
        }
        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.