Home » Data Structure » Array Data Structure

Shuffle a given array using Fisher-Yates shuffle Algorithm

C++ implementation to shuffle a given array using fisher-yates shuffle algorithm using rand() function.
Submitted by Vikneshwar GK, on April 09, 2022

Consider an integer array, of size n. The task at hand is to shuffle the elements of the array in a random manner. The arrangement of the element must be random such that every permutation of the array of elements must be equally likely. This problem can also be called "shuffle a deck of cards" and "randomize a given array".

Example:

Input:
array[]= {1, 2, 3, 4, 5}

Output:
array[] = {5, 2, 1, 3, 4} 

There are several permutations.
This is one of them.

Input:
array[] = {1, 2, 3, 4, 5, 6, 7}

Output:
array[] = {3, 1, 5, 2, 7, 6, 4}

Solution: Using rand() function

Fisher-Yates shuffle algorithm involves generating a random number and using that number to place elements present in the array. It involves the following steps:

• Iterate through the array from end to beginning, i.e, from n-1 to 1, where n is the length of the array.
• Call rand() function to randomly generate an integer between 0 and the current iteration position.
• Swap the current index element and element at randomly generated index.
• Perform the above steps for the remaining elements in the array.
• Print the array.

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// function to swap the elements
void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void randomize(int array[], int length)
{
    // initialize a seed value
    // to get same result each time
    // we run this program
    // use different seed value to get different result
    srand(time(NULL));

    // iterate through the array from end to beginning
    for (int i = length - 1; i > 0; i--) {
        // Pick a random index from 0 to i
        int j = rand() % (i + 1);

        // swap the elements
        swap(&array[i], &array[j]);
    }
}

// Main function
int main()
{
    int array[100];
    int N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }
    
    randomize(array, N);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 5
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
2 4 1 3 5 

Time Complexity: O(n), where n is the length of the array. The rand() function is assumed to take O(1) complexity.