how to sort strings in javascript numerically

drawnonward picture drawnonward · Nov 12, 2011 · Viewed 14.1k times · Source

I would like to sort an array of strings (in javascript) such that groups of digits within the strings are compared as integers not strings. I am not worried about signed or floating point numbers.

for example, the result should be ["a1b3","a9b2","a10b2","a10b11"] not ["a1b3","a10b11","a10b2","a9b2"]

The easiest way to do this seems to be splitting each string on boundaries around groups of digits. Is there a pattern I can pass to String.split to split on character boundaries without removing any characters?

"abc11def22ghi".split(/?/) = ["abc","11","def","22","ghi"];

Or is there another way to compare strings that does not involve splitting them up, perhaps by padding all groups of digits with leading zeros so they are the same length?

"aa1bb" => "aa00000001bb", "aa10bb" => "aa00000010bb"

I am working with arbitrary strings, not strings that have a specific arrangement of digit groups.

Edit:

I like the /(\d+)/ one liner from Gaby to split the array. How backwards compatible is that?

The solutions that parse the strings once in a way that can be used to rebuild the originals are much more efficient that this compare function. None of the answers handle some strings starting with digits and others not, but that would be easy enough to remedy and was not explicit in the original question.

["a100","a20","a3","a3b","a3b100","a3b20","a3b3","!!","~~","9","10","9.5"].sort( function ( inA , inB ) {
    var                     result = 0;

    var                     a , b , pattern = /(\d+)/;
    var                     as = inA.split( pattern );
    var                     bs = inB.split( pattern );
    var                     index , count = as.length;

    if ( ( '' === as[0] ) === ( '' === bs[0] ) ) {
        if ( count > bs.length ) count = bs.length;

        for ( index = 0 ; index < count && 0 === result ; ++index ) {
            a = as[index]; b = bs[index];

            if ( index & 1 ) {
                result = a - b;
            } else {
                result = !( a < b ) ? ( a > b ) ? 1 : 0 : -1;
            }
        }

        if ( 0 === result ) result = as.length - bs.length;
    } else {
        result = !( inA < inB ) ? ( inA > inB ) ? 1 : 0 : -1;
    }

    return result;
} ).toString();

result: "!!,9,9.5,10,a3,a3b,a3b3,a3b20,a3b100,a20,a100,~~"

Answer

Alan Draper picture Alan Draper · Nov 12, 2011

I think this does what you want

function sortArray(arr) {
    var tempArr = [], n;
    for (var i in arr) {
        tempArr[i] = arr[i].match(/([^0-9]+)|([0-9]+)/g);
        for (var j in tempArr[i]) {
            if( ! isNaN(n = parseInt(tempArr[i][j])) ){
                tempArr[i][j] = n;
            }
        }
    }
    tempArr.sort(function (x, y) {
        for (var i in x) {
            if (y.length < i || x[i] < y[i]) {
                return -1; // x is longer
            }
            if (x[i] > y[i]) {
                return 1;
            }
        }
        return 0;
    });
    for (var i in tempArr) {
        arr[i] = tempArr[i].join('');
    }
    return arr;
}
alert(
    sortArray(["a1b3", "a10b11", "a10b2", "a9b2"]).join(",")
);