Knuth (Fisher-Yates) shuffle algorithm is an algorithm for randomly shuffling the elements of an array. The Knuth Fisher-Yates shuffle is used to randomly permute given input (list). The permutations generated by this algorithm occur with the same probability. The complexity of this algorithm is O(n). Check the solutions below.

The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.

This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.

JavaScript

// Shuffle an array in JavaScript
function shuffle(array) {
  var m = array.length, temp, i;

  // Check if there's still elements remaining
  while (m) {

    // Pick remaining element
    i = Math.floor(Math.random() * m--);

    // Swap it with the current element
    temp = array[m];
    array[m] = array[i];
    array[i] = temp;
  }

  return array;
}

Java

// Shuffle an array in Java

public static void knuth(int[] array) {
  Random r = new Random();
  for (int i = array.length - 1; i > 0; i--) {
    int index = r.nextInt(i);
    // swap 
    int tmp = array[index];
    array[index] = array[i];
    array[i] = tmp;
  }
}

Python

// Shuffle an array in Python

from random import randrange
 
def shuffle(x):
    for i in range(len(x)-1, 0, -1):
        j = randrange(i + 1)
        x[i], x[j] = x[j], x[i]
 
x = list(range(10))
shuffle(x)
print("shuffled array -- ", x)