# Shuffle a given array using Fisher–Yates shuffle Algorithm

Given an array, write a program to generate a random permutation of array elements. This question is also asked as “shuffle a deck of cards” or “randomize a given array”. Here shuffle means that every permutation of array element should equally likely. Let the given array be arr[]. A simple solution is to create an auxiliary array temp[] which is initially a copy of arr[]. Randomly select an element from temp[], copy the randomly selected element to arr and remove the selected element from temp[]. Repeat the same process n times and keep copying elements to arr, arr, … . The time complexity of this solution will be O(n^2).

Fisher–Yates shuffle Algorithm works in O(n) time complexity. The assumption here is, we are given a function rand() that generates random number in O(1) time.
The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.

Following is the detailed algorithm

```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]
```

Following is implementation of this algorithm.

## C++

// C++ Program to shuffle a given array
#include
#include
#include
using namespace std;

// A utility function to swap to integers
void swap (int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

// A utility function to print an array
void printArray (int arr[], int n)
{
for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << " "; } // A function to generate a random // permutation of arr[] void randomize (int arr[], int n) { // Use a different seed value so that // we don't get same result each time // we run this program srand (time(NULL)); // Start from the last element and swap // one by one. We don't need to run for // the first element that's why i > 0
for (int i = n – 1; i > 0; i–)
{
// Pick a random index from 0 to i
int j = rand() % (i + 1);

// Swap arr[i] with the element
// at random index
swap(&arr[i], &arr[j]);
}
}

// Driver Code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = sizeof(arr) / sizeof(arr);
randomize (arr, n);
printArray(arr, n);

return 0;
}

// This code is contributed by
// rathbhupendra

## C

 `// C Program to shuffle a given array ` ` `  `#include ` `#include ` `#include ` ` `  `// A utility function to swap to integers ` `void` `swap (``int` `*a, ``int` `*b) ` `{ ` `    ``int` `temp = *a; ` `    ``*a = *b; ` `    ``*b = temp; ` `} ` ` `  `// A utility function to print an array ` `void` `printArray (``int` `arr[], ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``printf``(``"%d "``, arr[i]); ` `    ``printf``(````" "````); ` `} ` ` `  `// A function to generate a random permutation of arr[] ` `void` `randomize ( ``int` `arr[], ``int` `n ) ` `{ ` `    ``// Use a different seed value so that we don't get same ` `    ``// result each time we run this program ` `    ``srand` `( ``time``(NULL) ); ` ` `  `    ``// Start from the last element and swap one by one. We don't ` `    ``// need to run for the first element that's why i > 0 ` `    ``for` `(``int` `i = n-1; i > 0; i--) ` `    ``{ ` `        ``// Pick a random index from 0 to i ` `        ``int` `j = ``rand``() % (i+1); ` ` `  `        ``// Swap arr[i] with the element at random index ` `        ``swap(&arr[i], &arr[j]); ` `    ``} ` `} ` ` `  `// Driver program to test above function. ` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 2, 3, 4, 5, 6, 7, 8}; ` `    ``int` `n = ``sizeof``(arr)/ ``sizeof``(arr); ` `    ``randomize (arr, n); ` `    ``printArray(arr, n); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java Program to shuffle a given array ` `import` `java.util.Random; ` `import` `java.util.Arrays; ` `public` `class` `ShuffleRand  ` `{ ` `    ``// A Function to generate a random permutation of arr[] ` `    ``static` `void` `randomize( ``int` `arr[], ``int` `n) ` `    ``{ ` `        ``// Creating a object for Random class ` `        ``Random r = ``new` `Random(); ` `         `  `        ``// Start from the last element and swap one by one. We don't ` `        ``// need to run for the first element that's why i > 0 ` `        ``for` `(``int` `i = n-``1``; i > ``0``; i--) { ` `             `  `            ``// Pick a random index from 0 to i ` `            ``int` `j = r.nextInt(i+``1``); ` `             `  `            ``// Swap arr[i] with the element at random index ` `            ``int` `temp = arr[i]; ` `            ``arr[i] = arr[j]; ` `            ``arr[j] = temp; ` `        ``} ` `        ``// Prints the random array ` `        ``System.out.println(Arrays.toString(arr)); ` `    ``} ` `     `  `    ``// Driver Program to test above function ` `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `         `  `         ``int``[] arr = {``1``, ``2``, ``3``, ``4``, ``5``, ``6``, ``7``, ``8``}; ` `         ``int` `n = arr.length; ` `         ``randomize (arr, n); ` `    ``} ` `} ` `// This code is contributed by Sumit Ghosh `

## Python

 `# Python Program to shuffle a given array ` `import` `random ` ` `  `# A function to generate a random permutation of arr[] ` `def` `randomize (arr, n): ` `    ``# Start from the last element and swap one by one. We don't ` `    ``# need to run for the first element that's why i > 0 ` `    ``for` `i ``in` `range``(n``-``1``,``0``,``-``1``): ` `        ``# Pick a random index from 0 to i ` `        ``j ``=` `random.randint(``0``,i``+``1``) ` ` `  `        ``# Swap arr[i] with the element at random index ` `        ``arr[i],arr[j] ``=` `arr[j],arr[i] ` `    ``return` `arr ` ` `  `# Driver program to test above function. ` `arr ``=` `[``1``, ``2``, ``3``, ``4``, ``5``, ``6``, ``7``, ``8``] ` `n ``=` `len``(arr) ` `print``(randomize(arr, n)) ` ` `  ` `  `# This code is contributed by Pratik Chhajer `

## C#

 `// C# Code for Number of digits  ` `// in the product of two numbers ` `using` `System; ` ` `  `class` `GFG ` `{  ` `// A Function to generate a ` `// random permutation of arr[] ` `    ``static` `void` `randomize(``int` `[]arr, ``int` `n) ` `    ``{ ` `        ``// Creating a object ` `        ``// for Random class ` `        ``Random r = ``new` `Random(); ` `         `  `        ``// Start from the last element and ` `        ``// swap one by one. We don't need to ` `        ``// run for the first element  ` `        ``// that's why i > 0 ` `        ``for` `(``int` `i = n - 1; i > 0; i--)  ` `        ``{ ` `             `  `            ``// Pick a random index ` `            ``// from 0 to i ` `            ``int` `j = r.Next(0, i+1); ` `             `  `            ``// Swap arr[i] with the ` `            ``// element at random index ` `            ``int` `temp = arr[i]; ` `            ``arr[i] = arr[j]; ` `            ``arr[j] = temp; ` `        ``} ` `        ``// Prints the random array ` `        ``for` `(``int` `i = 0; i < n; i++) ` `        ``Console.Write(arr[i] + ``" "``); ` `    ``} ` `     `  `     `  `// Driver Code ` `static` `void` `Main() ` `{ ` `    ``int``[] arr = {1, 2, 3, 4,  ` `                 ``5, 6, 7, 8}; ` `    ``int` `n = arr.Length; ` `    ``randomize (arr, n); ` `} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` 0 ` `    ``for``(``\$i` `= ``\$n` `- 1; ``\$i` `>= 0; ``\$i``--) ` `    ``{ ` `        ``// Pick a random index ` `        ``// from 0 to i ` `        ``\$j` `= rand(0, ``\$i``+1); ` ` `  `        ``// Swap arr[i] with the  ` `        ``// element at random index ` `        ``\$tmp` `= ``\$arr``[``\$i``]; ` `        ``\$arr``[``\$i``] = ``\$arr``[``\$j``]; ` `        ``\$arr``[``\$j``] = ``\$tmp``; ` `    ``} ` `    ``for``(``\$i` `= 0; ``\$i` `< ``\$n``; ``\$i``++) ` `    ``echo` `\$arr``[``\$i``].``" "``; ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(1, 2, 3, 4,  ` `             ``5, 6, 7, 8); ` `\$n` `= ``count``(``\$arr``); ` `randomize(``\$arr``, ``\$n``); ` ` `  `// This code is contributed by mits ` `?> `

Output :

`7 8 4 6 3 1 2 5`

The above function assumes that rand() generates a random number.

Time Complexity: O(n), assuming that the function rand() takes O(1) time.

How does this work?
The probability that ith element (including the last one) goes to last position is 1/n, because we randomly pick an element in first iteration.

The probability that ith element goes to second last position can be proved to be 1/n by dividing it in two cases.
Case 1: i = n-1 (index of last element):
The probability of last element going to second last position is = (probability that last element doesn’t stay at its original position) x (probability that the index picked in previous step is picked again so that the last element is swapped)
So the probability = ((n-1)/n) x (1/(n-1)) = 1/n
Case 2: 0 < i < n-1 (index of non-last):
The probability of ith element going to second position = (probability that ith element is not picked in previous iteration) x (probability that ith element is picked in this iteration)
So the probability = ((n-1)/n) x (1/(n-1)) = 1/n

We can easily generalize above proof for any other position.

## tags:

Mathematical Randomized Mathematical