Randomized

Shuffle a given array using Fisher–Yates shuffle Algorithm

Pinterest LinkedIn Tumblr

Fisher–Yates shuffle is an algorithm for generating a random set. The Fisher–Yates shuffle is quite efficient. Shuffling an array randomizes its element order.

Write a program to randomly shuffle the Array.

source Code

package com.dsacode.Algorithm.randomized;
 
import java.util.Arrays;
import java.util.Random;
 
public class ShuffleArray {
      static void shuffleArray(int[] ar){
        Random rnd = new Random();
        for (int i = ar.length - 1; i > 0; i--){
          int index = rnd.nextInt(i + 1);
          int a = ar[index];
          ar[index] = ar[i];
          ar[i] = a;
        }
      }
    public static void main(String[] args) {
         int[] arr = { 1, 2, 3, 4, 5, 6, 16, 15, 14, 13, 12, 11 };
         System.out.println("Original array of itmes: " + Arrays.toString(arr));
         shuffleArray(arr);
         System.out.println("after  Fisher–Yates shuffle array of itmes: " + Arrays.toString(arr));
 
    }
 
}

Output

Original array of items: [1, 2, 3, 4, 5, 6, 16, 15, 14, 13, 12, 11]
After Fisher-Yates shuffle array of items: [6, 11, 15, 2, 5, 4, 3, 13, 16, 12, 1, 14]

Algorithm Explanation

Write down the numbers from 1 to length of array.
Pick a random number with in the array.
Remove the selected number form array and continue for other numbers.
The entire array randomized and return the randomized array.

Time Complexity

Best CaseAverage CaseWorst Case
O(n)

Reference

  1. http://www.geeksforgeeks.org/shuffle-a-given-array
  2. https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Write A Comment