In this article, we have explored two approaches to shuffle an array. The first approach uses an auxiliary array while the second approach is in-place and is known as Fisher Yates Algorithm.

Table of content:

1. Introduction
2. Approach 1: Using auxiliary array
3. Approach 2: Fisher Yates Algorithm

Let us get started.

Introduction

Given an array, we need to shuffle it randomly. All possible permutations of the array elements must be equally likely to be produced after shuffling. In this article, we discuss two approaches to do this task. First, we discuss a basic algorithm which requires extra space to shuffle the array in O(N) time. Next, we discuss the Fisher Yates Algorithm which shuffles the array inplace.

Why would we want a program to shuffle an array?

• To create test cases: We can use this function/program to create test cases for coding questions/for testing code.

Approach 1: Using auxiliary array

As a first approach, we discuss a basic algorithm:

1. Make an auxiliary array.
2. While there are more elements in the given array:
   2.1. Pick an element from the given array using the random function.
   2.2. Remove this element from the array and add it to the auxiliary array.
3. Return the auxiliary array.

Note: Most high level languages provide a function which randomly picks an element. The random function picks the element from the array in O(1).

Example: Dry Run

Given array = [1,2,3,4,5]
Auxiliary array = [ ]

rand(array) = 3, array = [1,2,4,5], aux array = [3]
rand(array) = 1, array = [2,4,5], aux array = [3,1]
rand(array) = 4, array = [2,5], aux array = [3, 1, 4]
rand(array) = 5, array = [2], aux array = [3, 1, 4, 5]
rand(array) = 2, array = [ ], aux array = [3, 1, 4, 5, 2]

Code

Java

public static ArrayList<Integer> shuffle(ArrayList<Integer> arr)
{
    ArrayList<Integer> res = new ArrayList<>();
    while(arr.size()!=0)
    {
        int num = new Random.nextInt(arr.size());
        res.add(num);
        arr.remove(new Integer(num));
    }
    return res;
}

Java provides an inbuilt function called Collections.shuffle(). This can be used to shuffle an ArrayList. The original ordering is lost when this operation is done and the original array list is modified.

Collections.shuffle(arr);  // shuffles the array

Time complexity

The random function takes O(1) time to pick an element from the array. The algorithm randomly picks all the elements in the array one by one and adds them to the auxiliary array. Picking the element from the array and adding it to the auxiliary arraya is a O(1) operation. As this operation is done N times, the time complexity becomes O(N).

Space complexity

The algorithm uses an auxiliary array to store the elements of the resultant array. Hence, the space complexity becomes O(N).

Approach 2: Fisher Yates Algorithm

Fisher Yates algorithm provides a slight improvement over the appproach discussed above. It shuffles the array inplace, i.e it does not require extra space.
The algorithm is discussed below:

Algorithm

    for i in range n-1 to 1
        j = random integer such that 0 <= j <= i
        swap a[j] and a[i] 

Example: Dry Run

Given, arr = [1,2,3,4,5]

for i in range (4, 1):
i = 4, arr[i] = 5, let j = 2, then swap arr[4] with arr[2] => arr = [1,2,5,4,3]
i = 3, arr[i] = 4, let j = 1, then swap arr[3] with arr[1] => arr = [1,4,5,2,3]
i = 2, arr[i] = 5, let j = 0, then swap arr[2] with arr[0] => arr = [5,4,1,2,3]
i = 1, arr[i] = 4, let j = 1, then swap arr[1] with arr[1] => arr = [5,4,1,2,3]

This yields a shuffled array = [5,4,1,2,3]

Code

Java

public static void shuffle(int arr[])
{
    for(int i=arr.length-1;i > 0;i--)
    {
        Random rand = new Random();
        int j = rand.nextInt(i+1);
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}

C++

public void shuffle(int arr[], int n)
{
  srand(time(NULL));
  for(int i=n-1;i>=1;i--)
  {
      int j = rand()%(i+1);
      int temp = arr[j];
      arr[j] = arr[i];
      arr[i] = temp;
   }
}

Time Complexity

We traverse the array only once, hence the time complexity comes out to be O(N).

Space Complexity

This algorithm does not require extra space to shuffle the array, this is called inplace shuffling. Hence, the space complexity is O(1).

With this article at OpenGenus, you must have the complete idea of how to shuffle an array using two different approaches.