Javascript natural sort array/object and maintain

Question

I have an array of items as follows in Javascript:

var users = Array();

users[562] = 'testuser3';
users[16] = 'testuser6';
users[834] = 'testuser1';
users[823] = 'testuser4';
users[23] = 'testuser2';
users[917] = 'testuser5';

I need to sort that array to get the following output:

users[834] = 'testuser1';
users[23] = 'testuser2';
users[562] = 'testuser3';
users[823] = 'testuser4';
users[917] = 'testuser5';
users[16] = 'testuser6';

Notice how it is sorted by the value of the array and the value-to-index association is maintained after the array is sorted (that is critical). I have looked for a solution to this, tried making it, but have hit a wall.

By the way, I am aware that this is technically not an array since that would mean the indices are always iterating 0 through n where n+1 is the counting number proceeding n. However you define it, the requirement for the project is still the same. Also, if it makes a difference, I am NOT using jquery.

Answer 1

If I understand the question correctly, you're using arrays in a way they are not intended to be used. In fact, the initialization style

// Don't do this!
var array = new Array();
array[0] = 'value';
array[1] = 'value';
array[2] = 'value';

teaches wrong things about the nature and purpose of arrays. An array is an ordered list of items, indexed from zero up. The right way to create an array is with an array literal:

var array = [
    'value',
    'value',
    'value'
]

The indexes are implied based on the order the items are specified. Creating an array and setting users[562] = 'testuser3' implies that there are at least 562 other users in the list, and that you have a reason for only knowing the 563rd at this time.

In your case, the index is data, and is does not represent the order of the items in the set. What you're looking for is a map or dictionary, represented in JavaScript by a plain object:

var users = {
    562: 'testuser3',
    16:  'testuser6',
    834: 'testuser1',
    823: 'testuser4',
    23:  'testuser2',
    917: 'testuser5'
}

Now your set does not have an order, but does have meaningful keys. From here, you can follow galambalazs's advice to create an array of the object's keys:

var userOrder;
if (typeof Object.keys === 'function') {
    userOrder = Object.keys(users);
} else {
    for (var key in users) {
        userOrder.push(key);
    }
}

…then sort it:

userOrder.sort(function(a, b){
    return users[a].localeCompare(users[b]);
});

Here's a demo

Answer 2

Sparse arrays usually spell trouble. You're better off saving key-value pairs in an array as objects (this technique is also valid JSON):

users = [{
    "562": "testuser3"
},{
    "16": "testuser6"
}, {
    "834": "testuser1"
}, {
    "823": "testuser4"
}, {
    "23": "testuser2"
}, {
    "917": "testuser5"
}];

As suggested, you can use a for loop to map the sorting function onto the array.

Answer 3

The order of the elements of an array is defined by the index. So even if you specify the values in a different order, the values will always be stored in the order of their indices and undefined indices are undefined:

> var arr = [];
> arr[2] = 2;
> arr[0] = 0;
> arr
[0, undefined, 2]

Now if you want to store the pair of index and value, you will need a different data structure, maybe an array of array like this:

var arr = [
    [562, 'testuser3'],
    [16, 'testuser6'],
    [834, 'testuser1'],
    [823, 'testuser4'],
    [23, 'testuser2'],
    [917, 'testuser5']
];

This can be sorted with this comparison function:

function cmp(a, b) {
    return a[1].localeCompare(b[1]);
}
arr.sort(cmp);

The result is this array:

[
    [834, 'testuser1'],
    [23, 'testuser2'],
    [562, 'testuser3'],
    [823, 'testuser4'],
    [917, 'testuser5'],
    [16, 'testuser6']
]

Answer 4

I'd use map once to make a new array of users, then a second time to return the string you want from the new array.

var users= [];
users[562]= 'testuser3';
users[16]= 'testuser6';
users[834]= 'testuser1';
users[823]= 'testuser4';
users[23]= 'testuser2';
users[917]= 'testuser5';

var u2= [];
users.map(function(itm, i){
    if(itm){
        var n= parseInt(itm.substring(8), 10);
        u2[n]= i;
    }
});
u2.map(function(itm, i){
    return 'users['+itm+']= testuser'+i;
}).join('\n');

/*returned value: (String)
users[834]= testuser1
users[23]= testuser2
users[562]= testuser3
users[823]= testuser4
users[917]= testuser5
users[16]= testuser6
*/

If you want to avoid any gaps. use a simple filter on the output-

u2.map(function(itm, i){
    return 'users['+itm+']= testuser'+i;
}).filter(function(itm){return itm}).join('\n');

Answer 5

Using the ideas from the comments, I came up with the following solution. The naturalSort function is something I found on google and I modified it to sort a multidimensional array. Basically, I made the users array a multidimensional array with the first index being the user id and the second index being the user name. So:

users[0][0] = 72;
users[0][1] = 'testuser4';
users[1][0] = 91;
users[1][1] = 'testuser2';
users[2][0] = 12;
users[2][1] = 'testuser8';
users[3][0] = 3;
users[3][1] = 'testuser1';
users[4][0] = 18;
users[4][1] = 'testuser7';
users[5][0] = 47;
users[5][1] = 'testuser3';
users[6][0] = 16;
users[6][1] = 'testuser6';
users[7][0] = 20;
users[7][1] = 'testuser5';

I then sorted the array to get the following output:

users_sorted[0][0] = 3;
users_sorted[0][1] = 'testuser1';
users_sorted[1][0] = 91;
users_sorted[1][1] = 'testuser2';
users_sorted[2][0] = 47;
users_sorted[2][1] = 'testuser3';
users_sorted[3][0] = 72;
users_sorted[3][1] = 'testuser4';
users_sorted[4][0] = 20;
users_sorted[4][1] = 'testuser5';
users_sorted[5][0] = 16;
users_sorted[5][1] = 'testuser6';
users_sorted[6][0] = 18;
users_sorted[6][1] = 'testuser7';
users_sorted[7][0] = 12;
users_sorted[7][1] = 'testuser8';

The code to do this is below:

function naturalSort(a, b) // Function to natural-case insensitive sort multidimensional arrays by second index
{

    // setup temp-scope variables for comparison evauluation
    var re = /(-?[0-9\.]+)/g,
        x = a[1].toString().toLowerCase() || '',
        y = b[1].toString().toLowerCase() || '',
        nC = String.fromCharCode(0),
        xN = x.replace( re, nC + '$1' + nC ).split(nC),
        yN = y.replace( re, nC + '$1' + nC ).split(nC),
        xD = (new Date(x)).getTime(),
        yD = xD ? (new Date(y)).getTime() : null;
    // natural sorting of dates
    if ( yD )
        if ( xD < yD ) return -1;
        else if ( xD > yD ) return 1;
    // natural sorting through split numeric strings and default strings
    for( var cLoc = 0, numS = Math.max(xN.length, yN.length); cLoc < numS; cLoc++ ) {
        oFxNcL = parseFloat(xN[cLoc]) || xN[cLoc];
        oFyNcL = parseFloat(yN[cLoc]) || yN[cLoc];
        if (oFxNcL < oFyNcL) return -1;
        else if (oFxNcL > oFyNcL) return 1;
    }
    return 0;
}

// Set values for index
    var users = Array();
    var temp = Array();

    users.push(Array('72', 'testuser4'));
    users.push(Array('91', 'testuser2'));
    users.push(Array('12', 'testuser8'));
    users.push(Array('3', 'testuser1'));
    users.push(Array('18', 'testuser7'));
    users.push(Array('47', 'testuser3'));
    users.push(Array('16', 'testuser6'));
    users.push(Array('20', 'testuser5'));

// Sort the array
    var users_sorted = Array();
    users_sorted = users.sort(naturalSort);

Answer 6

Array.prototype.sort() takes an optional custom comparison function -- so if you dump all of your users into an array in this manner [ [562, "testuser3"], [16, "testuser6"] ... etc.]

Then sort this array with the following function:

function(comparatorA, comparatorB) {
    var userA = comparatorA[1], userB = comparatorB[1]
    if (userA > userB)     return 1;
    if (userA < userB)     return -1;
    if (userA === userB)   return 0;
}

Then rebuild your users object. (Which will loose you your sorting.) Or, keep the data in the newly sorted array of arrays, if that will work for your application.