Shuffle an array by sorting in javascript

Question

I'm currently reading CRLS and implementing the algorithms in javascript.

In section 5.3 - Permute by sorting, I felt like a morron while trying to come up with an efficient implementation of the simple algorithm. Here is the pseudo-code:

Here is my implementation

Array.prototype.sortShuffle = function () {
    const LENGTH = this.length;
    const CUBE = Math.pow(LENGTH, 3);

    let P = this
        .map((e, i) => {
            return {v: Math.floor(Math.random() * CUBE), e: e}
        })
        .sort((e1, e2) => e1.v > e2.v);

    P.forEach((e, i) => this[i] = e.e);
}

I resorted to this sad solution because the native Array.prototype.sort doesn't provide the indexes in the comparator, A.sort((e1, e2, i1, i2) => ...) could have done the trick.

Can anyone please provide a more efficient solution (without implementing the sorting function above all)

Answer 1

Your code is actually well done, but could just use some style improvements:

Array.prototype.sortShuffle = function () {
    const nCubed = Math.pow(this.length, 3);

    this.map(v => ({ k: Math.random() * nCubed, v }))
        .sort(({ k: k1 }, { k: k2 }) => k1 - k2)
        .forEach(({ v }, i) => this[i] = v);
};

In particular, you can use shorthand property names and object destructuring, as well as removing some unnecessary variables. Also, you don't need to use Math.floor, because floating point numbers will work just as well.

Answer 2

You can keep the other array as "tuples" which makes for code that's a little cleaner.

Array.prototype.sortShuffle = function () {
  return this.map(v => [Math.random() * this.length ** 3, v])
             .sort(([k1,v1],[k2,v2]) => k1 - k2)
             .map(([k, v]) => v);
}

In terms of speed - you're better off using Fisher-Yates or another O(n) algorithm.

Note that you had a mistake in your implementation as sort expects the comparator function to return a positive or negative number (rather than just a boolean).