# On Shuffling Arrays

Just a quick note - not directly Pixelblaze related, but I’ve seen (and made) several patterns recently that use a “shuffle” algorithm to arrays. It’s tougher than it seems at first glance. Here’s what I’ve learned:

• The Fisher-Yates shuffle is good, fast and reliable. It executes in O(n) time, vs O(n log n) for sorting algorithms. (Although on the Pixelblaze, the overhead of working in user code vs. internal library routines may outweigh this.)

• `pixels.sortBy(() => random(1) - .5) //shuffle` produces a very biased shuffle. (My former employer actually used this in a product once, to their own detriment.

• `pixels.sortBy()` with a comparison function like:

``````compare(a, b) {
return random[a] - random[b];
}
``````

produces a well distributed shuffle. It’s still gonna be O(n log n), but lower overhead might make it faster than user-code Fisher-Yates on Pixelblaze. Plus, it’s short and easy to remember - I’ll probably start using this in PB patterns!

References:
https://bost.ocks.org/mike/shuffle/compare.html (interesting to play with!)

https://stackoverflow.com/questions/962802/is-it-correct-to-use-javascript-array-sort-method-for-shuffling

https://blog.codinghorror.com/the-danger-of-naivete/

2 Likes

Interesting! Where on earth did you find `pixels.sortBy(() => random(1) - .5)` in the wild?!?!

Folks arriving here may be looking for some example code (at least until I add a native array shuffle). Here’s the Fisher-Yates-Knuth algorithm lifted from a genuine @zranger1 pattern, modified to work generically on any array passed in:

``````// shuffle array
// (standard Fisher-Yates-Knuth shuffle)
function shuffle(arr) {
for (var i = arr.length - 1; i > 0; i--) {
var r = floor(random(i+1));
var tmp  = arr[i];
arr[i] = arr[r];
arr[r] = tmp;
}
}
``````

I don’t think the `return random[a] - random[b]` is going to be easy or a good replacement since you need another array seeded with random values the size of the possible values of the array to be sorted, and I think would only work on integer values. That is not as easy as `random(a) - random(b)` which is short and simple and apparently terrible for shuffling.

Anyway you’ve convinced me that I should add a native `array.shuffle()` to the list of stuff to add!

2 Likes

Microsoft did the `() => random(1) - .5)` thing in in the Windows 7 era when trying to create a randomly ordered default browser selection page to make the EU happy.

It didn’t turn out really random at all – placed Chrome at #1 and IE at #5 a very high percentage of the time. Of course this spawned a whole bunch of conspiracy theories about how MS somehow secretly knew that position #5 was best. But it’s way more likely that somebody just got in a hurry and didn’t test carefully.

And you’re dead right about the random[a]-random[b] thing. Works if you’ve got integers and the memory to spare. Otherwise um, definitely no.

Would love to see shuffle in the Pixelblaze API! One of those things that you might not use every day, but really really handy to have around.

1 Like