Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Examples
2.
Algorithm
2.1.
Implementation in C++
2.1.1.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What is the Fisher-Yates method of shuffling?
3.2.
Why does Fisher-Yates work smoothly?
3.3.
How useful is an array in solving programming problems?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Shuffle an array using Fisher-Yates shuffle Algorithm

Author Tarun Singh
1 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

In this article, we will understand array shuffling using Fisher-Yates Algorithm.  Fisher-Yates algorithm is unbiased, as it has an equal probability of generating all permutations. The Fisher-Yates shuffle is a shuffle performed in place. That is, rather than making a shuffled copy of the array, it shuffles the items of the array in place. This can favor us if the array to be shuffled is large. This algorithm has real-life applications. Reading this blog, you will learn an array shuffling technique very conveniently. We will discuss the algorithm for array shuffling with its code and time complexity.

Also Read About, Array Implementation of Queue and  Rabin Karp Algorithm

Problem statement

We are given an array in this problem, and we want to shuffle the array such that it generates a random array every time we run the code. The Fisher-Yates algorithm generates a random permutation of array elements, i.e., it shuffles all of an array's elements at random. Because the Fisher-Yates technique is impartial, all permutations for the array are equally likely.

Examples

1. Input: 

n=6, arr[] = {1, 3, 2, 4, 5, 9}

We will get a randomly shuffled array.

Output:

arr[] = {3, 2, 4, 5, 9, 1}

 

2. Input

n=6, arr[] = {3, 9, 10, 3, 4, 7}


Output:

arr[] = {3, 3, 9, 7, 4, 10}

Algorithm

1. Take the input for the number of elements for the array.

2. Take the input for the elements of the array.

3. Define a demo() function, which will have the below functioning.

4. The concept is to begin at an end.

5. Let's pretend we're starting from the beginning, and the array size is n. 

6. rand() function will generate a random number from 0 to j, every time the loop is in action.

7. For j=n-1 to 1

                   1. Pick an element in the range [0,j-1] randomly

                   2. Swap the randomly picked element with a[j]

                   3. Decrement j

8. End for loop

9. By doing so, a new array will be created.

Implementation in C++

// including header files
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
void solve(int arr[], int n)
{
    srand(time(0));
    for (int j = n - 1; j >= 1; j--)
    {
        // we will get random value of i with in range 0 to j-1
        int i = rand() % j;
        // swap jth index with ith
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}
int main()
{ // taking input for the size of array
    int n;
    cin >> n;
    // initializing and taking input for the array.
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    // calling our solve function
    solve(a, n);
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    return 0;
}

 

Input

n=6, arr[] = {5, 7, 8, 3, 2, 0}

 

Output

arr[] ={3, 2, 0, 8, 5, 7}

 

Complexity analysis

Time complexity

The time complexity O(N), where n is the size of the array as we traverse the array only one time to swap the elements if needed.

Space complexity

O(1), will be the space complexity as we have taken only two variables to traverse the array and haven't used any extra data structure.

Also read - Kadane's Algorithm

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is the Fisher-Yates method of shuffling?

The Fisher-Yates shuffle is a way to shuffle a sequence of things correctly. It is unbiased, has optimal linear time efficiency, utilizes constant space, and is incremental. 

Why does Fisher-Yates work smoothly?

The Fisher-Yates algorithm shuffles an array in a consistent manner. It's the most economical in terms of both runtime (O(length(arr)) and space (the shuffle is done in-place, requiring only O(1) extra memory).

How useful is an array in solving programming problems?

An array is a data structure that can hold a fixed number of elements of the same data type in a fixed size. Although an array is used to hold data, it is often more beneficial to conceive of it as a collection of variables of the same type.

Conclusion

In this article, we have discussed how to shuffle an array using Fisher-Yates Algorithm. We have gone through the Fisher-Yates algorithm in detail with its working algorithm C++ code, and we have also discussed its space and time complexity.

After reading about the array shuffling, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn more, you can refer to these links Data Structures and AlgorithmsCompetitive Programming.
Check out this problem - Maximum Product Subarray

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating systemsUnix File systemsFile System RoutingFile Input/Output.JavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Minimum product of k integers in an array of positive Integers
Next article
Count Square Submatrices with All Ones
Live masterclass