Shuffle an array using Fisher-Yates shuffle Algorithm

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;
}

You can also try this code with Online C++ Compiler

Run Code

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