Shuffle a given Array

Problem Statement

In the “Shuffle a given Array” problem we have given an array of integers. Write a program that shuffles the given array. That is, it will shuffle the elements in the array randomly.

Input Format

The first line containing an integer n.

Second-line containing n space-separated integer

Output Format

The first and only one line containing n space-separated integer.

Constraints

• 1<=n<=10^5
• -10^6<=a[i]<=10^6

Example

5
1 2 3 4 5

1 4 2 5 3

In this example, the output is just one of the possible outputs. The output will change every time when we run this program again and again.

Algorithm

Fisher-Yates shuffle Algorithm works in linear time complexity. The assumption here is, we are given a function rand() that generates a random number in constant 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.

1. Traverse the array one by one element from end to start.

2. Take j, which is the random integer such that 0 <= j <= i.

3. Swap arr[j], arr[i].

4. Print the final updated array arr[].

Implementation

C++ and Java Program for Shuffle a given Array

#include <bits/stdc++.h>
using namespace std;

int shuffle(int a[], int n)
{
  srand ( time(NULL) ); //To not get the same output every time we run this program
  for(int i=n-1;i>=0;--i)
  {
    int j = rand()%(i+1);
    swap(a[i],a[j]);
  }
}
int main()
{
   int n;
   cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   {
       cin>>a[i];
   }
   shuffle(a,n);
   for(int i=0;i<n;i++)
   {
       cout<<a[i]<<" ";
   }
   cout<<endl;
   return 0;
}

import java.util.Random;
import java.util.Scanner;
class sum
{
    static void shuffle(int a[], int n) 
    { 
        Random r = new Random();
        for(int i=n-1;i>=0;i--)
        {
            int j = r.nextInt(i+1); 
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        shuffle(a,n);
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
    }
}

4
-10 5 2 183

5 -10 2 183

Complexity Analysis for Shuffle a given Array

Time Complexity

O(n) where n is the size of the given array. Here we traverse the whole array one by one element and for each element, we perform swapping with a rand() value which is less than the current position of the element.

Space Complexity

O(1) because we don’t create auxiliary space here.