Home » Data Structure » Array Coding Problems

# Shuffle a given array in O(n) time using Fisher-Yates shuffle algorithm

In this article, we are going to see **how to shuffle a given array in O(n) time using Fisher-Yates shuffling algorithm?** This has very important applications in real-life products.

Submitted by Radib Kar, on July 13, 2020

**Example:**

Say the input array is [1, 2 3, 4, 5 6, 7] After reshuffling it can be anything like [4, 3, 7, 2, 1, 5, 1]

Our goal is that the reshuffling should be as random as possible.

**There is a standard algorithm named Fisher-Yates algorithm which shuffles the array in linear times.**

The idea is to start from an end

Say we are string from the right end and the array size is *n*

Now, pick the end element which will be the nth element, and pick up another element randomly from the range *[0, n-1]*. Then swap the elements and shrink the right end. Thus after this step, *a[n-1]*(the rightmost element) is fixed. Continue the same until we reach the left end.

The detailed algorithm will be,

For i=n-1 to 1 Pick and element in the range [0,i-1] randomly Swap the randomly picked element with a[i] Decrement i End for loop

Since, it's random we can't do dry run

But still to illustrate lets pick elements randomly as per thought

So initially, Array is [1, 2 3, 4, 5 6, 7] So i=6 Say, we picked up 4^{th}(0-indexed) element randomly (in the range [0-5]) Swap them So array is now [1, 2, 3, 4, 7, 6, 5] So 5 is now fixed and is guaranteed to stay there after the whole shuffling completes On the next iteration i will be 5 and we will continue similar way until I becomes 1

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; //reference to array is passed as we need //to update the array within the function void reshuffle(vector<int>& arr, int n) { srand(time(0)); for (int i = n - 1; i >= 1; i--) { //j will be a random no with in range 0 to i-1 int j = rand() % i; //swap ith index with jth int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } int main() { cout << "input array size\n"; int n; cin >> n; cout << "Input array elements \n"; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } reshuffle(arr, n); cout << "After reshuffling, printing the array\n"; for (auto it : arr) cout << it << " "; cout << endl; return 0; }

**Output:**

input array size 6 Input array elements 12 34 32 56 48 11 After reshuffling, printing the array 56 48 12 11 32 34

**Real-life applications:**

Creating an application which will suggest movie/songs from a list randomly. But each time it would suggest a unique movie only.

In this case, what we will do is we will show the i^{th} indexed movie after each iteration. As the i^{th} indexed one is never going to come again in the reshuffling as that's being fixed every time. That means we will recommend ith song/movie after the swap is done at each stage.

Go through the below link to understand the detailed problem and solution.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions