How to shuffle an array Back

Shuffling an array is a normal problem in coding, which can be used in many cases like card games. Generally, we can complete this function by creating an new array, and extracting items from the origin one randomly.

function shuffle(arr) {
    var ret = [];

    while (arr.length) {
        var index = Math.floor(Math.random() * arr.length);

        ret.push(arr[index]);
        arr.splice(index, 1);
    }

    return ret;
}

In this common way, the algorithm mainly costs in accessing the array and extracting items. If the time of Array.prototype.splice() can be represented by O(n), then the time of whole algorithm should be represented as O(n^2). That's not fast!

To complete it in a more elegant way, we should considering the solution Fisher-Yates Shuffle. The time of such solution can be represented by O(n). This algorithm can be described as: to access each item of an array and swap it backward or forward with an random item behind or before this item.

• Backward:

function shuffle(arr) {
    var len = arr.length;

    for (var i = 0; i < len; i++) {
        var index = Math.floor(Math.random() * i);

        if (i !== index) {
            /** swap */
            var temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }
}

• Forward:

function shuffle(arr) {
    var len = arr.length;

    for (var i = len - 1; i >= 0; i++) {
        var index = Math.floor(Math.random() * i);

        if (i !== index) {
            /** swap */
            var temp = arr[index];
            arr[index] = arr[i];
            arr[i] = temp;
        }
    }
}

To learn it in advance, we can read some articles:

• Fisher–Yates Shuffle
• How to randomize (shuffle) a JavaScript array?

Comments Copyright © aleen42 all right reserved, powered by aleen42

Empty Comments

Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.

authorize