Shuffle a given Array  

Difficulty Level Easy
Frequently asked in Amazon Apple Bloomberg Facebook Google Microsoft Oracle Two Sigma Yahoo
Array Rearrange

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.

Please click Like if you loved this article?

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[].

See also
Find the minimum distance between two numbers

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.

Please click Like if you loved this article?