What's the efficiency and quality of this shuffling algorithm?


This recent question about sorting randomly using C# got me thinking about the way I've sometimes shuffled my arrays in Perl.

@shuffled = sort { rand() <=> rand() } @array;

The proposed solution in the mentioned question is Fisher-Yates shuffle, which works in a linear time.

The question is: how efficient is my snippet and is such shuffle "really" random?

By : Tuminoid


@shuffled = map {
} sort {
  $a->[0] <=> $b->[0]
} map {
  [ rand(), $_ ]
} @array;
By : PP.

For one thing, you know that no matter the comparator you use sort() can't possibly be faster than O(n log n). So even if the shuffle it performs is fair, its performance will be worse.

So is the shuffle fair? It's obviously not fair for some (easy to analyze) sorting algorithms. Consider a simple bubble sort - in order for an element to move from one end to the other, the comparison function has to evaluate positive for n consecutive calls - a 1 in 2^n probability for what should be a 1 in n event. For quick sort, it's hard to analyze and it's possible that ends up being fair. But if it's important that it be right, do it the right way.

By : bmm6o

The perl documentation on sort says this

The comparison function is required to behave. If it returns inconsistent results (sometimes saying $x[1] is less than $x[2] and sometimes saying the opposite, for example) the results are not well-defined.

So it's a bad idea to do that.

ETA: I just did a benchmark. On a 100000 element array, using a FY-shuffle is more than 10 times faster too.

This video can help you solving your question :)
By: admin