DEV Community

Discussion on: Write better code: Day 3 - In-Place Shuffle

View post
Collapse
 
arjunrajkumar profile image
Arjun Rajkumar •

This was the logic for inplace shuffle..

  • Go thru the entire array
  • Initially with index 0, pick a random number between (0...array.size) and interchange the two numbers at [0] and [random]
  • Then with index 1, pick a random number between (1...array.size) and interchange them.
  • Then with index 2, pick a random number between (2...array.size) and interchange them.
  • Repeat...
def inplace_shuffle(shuffle_me)
  shuffle_me.each.with_index do |val, index|
    random = rand(index..(shuffle_me.length-1))
    shuffle_me[index], shuffle_me[random] = shuffle_me[random], shuffle_me[index]
  end
end

Goes thru once so it has O[n] time and O[1] space.