Durstenfeld shuffle algorithm : Optimized Fisher-Yates

Sat Jun 19 2021 07:26:03 GMT+0000 (UTC)

```function shuffle(array) {
const curIdx = array.length;

// While there remain elements to shuffle...
while (0 !== cur_idx) {
// Pick a remaining element...
const randIdx = Math.floor(Math.random() * curIdx);
curIdx -= 1;

// And swap it with the current element.
const originalIdx = array[curIdx];
array[curIdx] = array[randIdx];
array[randIdx] = originalIdx;
}
return array;
}

// Usage of shuffle
const arr = [1, 2, 3, 4, 5, 6];
arr = shuffle(arr);
console.log(arr);

// shorter
function shuffle(array) {
for (let i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var originalIdx = array[i];
array[i] = array[j];
array[j] = originalIdx;
}
}

//es6
function shuffle_array(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}```
content_copyCOPY

Durstenfeld shuffle is a variant of Fisher-Yates algorithm. The time complexity is O(N).