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 Case | Average Case | Worst Case |
---|---|---|
– | O(n) | – |