Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Fisher-Yates Algorithm for Array Shuffling

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 414
    Comment on it

    Hi there,

    Here in this blog I am going to provide Java implementation of Fisher-Yates Algorithm for array shuffling. Fisher–Yates shuffle algorithm as named after Ronald Fisher and Frank Yates. It is also known as Knuth shuffle. This algorithm takes O(n) time for shuffling the array. For detailed information you may follow this link http://www.geeksforgeeks.org/shuffle-a-given-array/.

    So how Fisher-Yates Algorithm works. Lets suppose we have an array of size n. Now the last element of the array is selected and is swapped with any randomly selected element from the whole array including the last element. Now the last element won't be considered as the part of array for computation purpose, so size of the array is considered as reduced by one i.e. n-1. This given steps will repeat until we left with only one element or we can say until we reached the first element of the array. After this we have an randomly shuffled array.

     

    Java Implementation for the Fisher-Yates algorithm

     

    import java.util.Random;
    
    public class FisherYatesArrayShuffle {
    
    	static void fisherYatesShuffling(int[] a, int n) {
    		int tmp;
    		int len = n;
    		int index;
    		Random rand = new Random();
    
    		for (int i = n - 1; i != 0; i--) {
    			index = rand.nextInt(len--);
    			tmp = a[index];
    			a[index] = a[i];
    			a[i] = tmp;
    		}
    	}
    
    	public static void main(String agrs[]) {
    
    		int[] a = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    		int n = a.length;
    		System.out.print("Input array elements : ");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + " ");
    		}
    		System.out.println();
    		fisherYatesShuffling(a, n);
    		System.out.print("Output array elements: ");
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + " ");
    		}
    		System.out.println();
    	}
    
    }

    Output of the above program

     

    Input array elements : 0 1 2 3 4 5 6 7 8 9 
    Output array elements: 5 3 2 6 9 4 8 1 0 7 
    

     

    Thanks for reading :)

 0 Comment(s)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: