Fisher–Yates shuffle algorithm in Javascript and Go

November 22, 2017

Fisher-Yates shuffle algorithm is a classic shuffling algorithm with great performance and mathematical correctness. Here is two implementation in Javascript and Go.

Javascript

// time: O(n)   space: O(n)
function shuffle(arr) {
  const len = arr.length
  const shuffled = new Array(len)

  let i = 0
  let ran
  const end = len - 1

  while (i <= end) {
    ran = ~~(Math.random() * (i + 1))

    if (ran !== i) {
      shuffled[i] = shuffled[ran]
    }

    shuffled[ran] = arr[i]

    i++
  }

  return shuffled
}

// time: O(n)   space: O(1)
function shuffleInPlace(arr) {
  const len = arr.length

  let ran
  let i = 0
  const end = len - 1

  while (i <= end) {
    ran = ~~(Math.random() * (i + 1))

    ;[arr[ran], arr[i]] = [arr[i], arr[ran]]
    
    // // that is ES6, same as the temp things as:
    // let temp = arr[i]
    // arr[i] = arr[ran]
    // arr[ran] = temp

    i++
  }

  return arr
}

Go

package play

import (
        "math/rand"
        "time"
)

func Shuffle(arr []int) []int {
        len := len(arr)
        shuffled := make([]int, len)

        var ran int

        for i := 0; i < len; i++ {

                rand.Seed(time.Now().UnixNano())
                ran = rand.Intn(i + 1)

                if ran != i {
                        shuffled[i] = shuffled[ran]
                }

                shuffled[ran] = arr[i]
        }

        return shuffled
}

Acknowledgements:

Tagged withjavascript, go, algorithm

Questions, Comments, Suggestions?Open an Issue