Proposal: Array.prototype.shuffle (Fisher-Yates)

[Tab Atkins Jr.]

On Sun, Apr 29, 2018 at 4:31 PM, J Decker <d3ck0r at gmail.com> wrote:
> I can see that's certainly something that can be gotten wrong; the in-place
> sort is kind-of nice; but you end up hitting most numbers twice, and with a
> longer array (say a set of 75 bingo balls) you can move the same number
> multiple times.
> which gives numbers at the end a higher chance of being at the start when
> all is done; and almost guaranteed to not be at the end.

This is true of a "naive" in-place shuffle, which draws the "item to
be placed at the end" from the full array, rather than from just the
unshuffled portion. But the proper Fisher-Yates algorithm does not
have this bias, and gives a proper unbiased sort, as shown by a
multitude of links across the web, many of which can be found in the
SO answers linked from earlier in this thread.

> And then to shuffle, for each number in the array, assign a random number;
> hang in a binary tree from least to most; then gather the tree back out.

While this shuffling method (assign a random number to each value,
then sort by that) also works and is unbiased, it takes O(nlogn) time,
and may, as you note for your implementation, have significant space
costs as well.  Fisher-Yates is a faster (linear-time, bounded by the
cost of generating N random numbers) and more space-efficient unbiased
algorithm.

~TJ