Write better code: Day 3 - In-Place Shuffle

This post originally appeared on Arjun Rajkumar 's blog. Arjun is a web developer based in Bangalore, India.

--

Day 3: Question 1

Write a method for doing an in-place shuffle of an array.

The shuffle must be "uniform," meaning each item in the original array must have the same probability of ending up in each spot in the final array.

Assume that you have a method get_random(floor, ceiling) for getting a random integer that is >= floor and <= ceiling.

An in-place algorithm operates directly on its input and changes it, instead of creating and returning a new object. This is sometimes called destructive, since the original input is "destroyed" when it's edited to create the new output.

If you want to follow along, feel free to post your answers in the comment.

My answers are in the comments.

Question from InterviewCake

Comments

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