### Randomizing an Array Revisited

It was pointed out in a comment on my post about randomizing arrays in Ruby that the `sort_by{rand}` is O(n log n), and it can be done in linear time, i.e. O(n). This is, of course, correct. Efficiency wasn't my primary concern in the original post, so much as a quick and easy to remember solution. That said, it's worth presenting the more complicated but more efficient algorithm.

I could just give the link to the blog post linked in the comment, but for the convenience of the reader I'll repeat the solution here (with minor changes that make me happier without changing the algorithm):

class Array def shuffle array = dup size.downto 2 do |j| r = rand j array[j-1], array[r] = array[r], array[j-1] end array end end

Enjoy!

## 0 Comments:

Post a Comment

## Links to this post:

Create a Link

<< Home