Array not sorting correctly in javascript

Question

I have a Javascript array of strings that I'm sorting using the compareFunction. For the most part, it's sorting correctly:

JS

array = ["E10N1", "E10N3", "E10N10", "E10N2", "E10N4", "E10N9", "E10N5", "E10N8", "E10N6", "E10N7"];

function sortStrings(a, b){
    if(a < b){
        return -1;
    }
    if(a > b){
        return 1;
    }
    return 0;
}

array.sort(sortStrings);
for(var i = 0; i < array.length; i++){
    $(".table_body").append("<div class='table_row'><p>" +array[i] +"</p></div>");
}

The issue I'm having is the sort function is putting the "E10N10" item between"E10N1" and "E10N2" items. So it looks like this:

I understand that sorting strings is done alphabetically, but wouldn't the "E10N10" string still be processed as later than "E10N9"? How do I fix it to have this particular string come last in the array after it's sorted?

Answer 1

You can modify your custom sorting function to handle this. For example, if all of your strings start with 4 characters that you don't care about when sorting, just do this:

function sortStrings(a, b){

    a = parseInt(a.substr(4));
    b = parseInt(b.substr(4));

    if(a < b){
        return -1;
    }
    if(a > b){
        return 1;
    }
    return 0;
}

Answer 2

In alphabetical sort, it just looks at the characters sequentially so "E10N1" would be before "E10N9", even though there is another character after the "E10N1". Just like "abcd" comes before "abd".

If you really want the type of sort you're asking for, it is going to take a much more complicated custom sort algorithm that actually parses the numeric parts of the tag to do actual numeric comparisons (not alphabetic sorts) on them.

Here's is a sorting scheme that sorts based on the trailing digits:

var array = ["E10N1", "E10N3", "E10N10", "E10N2", "E10N4", "E10N9", "E10N5", "E10N8", "E10N6", "E10N7"];

var regex = /\d+$/;
function getLastNum(str) {
    var m = str.match(regex);
    if (m) {
        return parseInt(m[0], 10);
    } else {
        return -1;
    }
}

array.sort(function(a, b) {
    return getLastNum(a) - getLastNum(b);
});
document.write(JSON.stringify(array));

You can obviously make this as complicated or rich as desired. For example, if you want to identify all numeric sequences in the number and turn each of them into actual numbers, you can do that too. You did not specify how involved this needs to be so I showed the smallest work required to make your specific sequence work (by sorting just by the trailing digits).

For a discussion of several different general purpose algorithms for handling mixed alpha-numeric sorts where the digits can occur anywhere in the string and can occur in multiple places, you can see this article: Sorting for Humans: Natural Sort Order. One particular implementation in Javascript can be found here.

The general idea behind the generic algorithm is as follows:

Get the next character of each string
If not both digits, then compare the characters directly and return the result
If both digits, then collect sequence of digits in both strings
    Longest sequence of consecutive digits is higher
    While accumulating sequential digits, keep track of which sequence
       has the first non-equal digit that is higher than the other
    If sequences were the same length, then the previous collected value  
       of which sequence had the first different higher number determines
       which sequence comes first
If sequence of digits or single character were equal, go to next character
    and start the above process over

One advantage of this generic algorithm is that it does not actually convert the numeric sequences of digits to a number so it will work on sequences of numbers of arbitrary length without running into limitations on how many digits a number can be in Javascript.

Depending upon your desired algorithm, you may or may not want to ignore whitespace preceding digits and you may or may not want to account for plus or minus signs in front of numbers. And, you may want to use a language aware comparison rather than a strict ascii code comparison. There are lots of factors to consider for any particular use.

---

Here is a general purpose algorithm that I wrote from scratch:

var array = ["E10N1", "E10N3", "E10N10", "E10N2", "E10N4", "E10N9", "E10N5", 
   "E10N8", "E10N6", "E10N7", "C10N1", "D10N3", "E11N10", "E09N2", "E999N4",
   "E10000N9", "g10N6", "z10N6", "q10N6", "R10N6", "E001N1", "E00N1",
   "E0000N1", "zN1", "zN000", "zN00", "000", "00", "0001", "0002", "A00",
   "A", "0A"];
// return negative value if a < b
// return 0 if a === b
// return positive value if a > b
// 
// Rules:
// - Sort characters before numbers
// - Ignore leading zeroes on digits
// - Ignore plus/minus signs in front of digits
// - For sequences of zeroes the shorter sequence is first
//
function alphaNumCompare(a, b) {
    var aIndex = 0,
        bIndex = 0,
        aChar, bChar, result;

    function isDigit(ch) {
        return ch >= "0" && ch <= "9";
    }

    function compareNums() {
        // aChar, bChar contain first digit
        // get rest of consecutive digits and compare
        // returns negative, 0 or positive
        // as side affect, advances aIndex and bIndex to next non-numeric
        var aZeroLen = 0,
            bZeroLen = 0,
            aNumStr = "",
            bNumStr = "";
        // collect consecutive digits from a and b
        // ignore any leading zeroes
        if (aChar === "0") {
            ++aZeroLen;
        } else {
            aNumStr = aChar;
        }
        if (bChar === "0") {
            ++bZeroLen;
        } else {
            bNumStr = bChar;
        }
        while (aIndex < a.length) {
            aChar = a.charAt(aIndex);
            if (!isDigit(aChar)) {
                break;
            }
            ++aIndex;
            // don't add leading zeroes and keep a count of leading zeroes
            if (aChar === "0" && aNumStr === "") {
                ++aZeroLen;
            } else {
                aNumStr += aChar;
            }
        }
        while (bIndex < b.length) {
            bChar = b.charAt(bIndex);
            if (!isDigit(bChar)) {
                break;
            }
            ++bIndex;
            // don't add leading zeroes and keep a count of leading zeroes
            if (bChar === "0" && bNumStr === "") {
                ++bZeroLen;
            } else {
                bNumStr += bChar;
            }
        }
        // we now have a series of consecutive digits in aNumStr and bNumStr
        if (aNumStr.length === bNumStr.length) {
            // check for nothing but leading zeroes in both
            if (aNumStr.length === 0) {
                return aZeroLen - bZeroLen;
            }
            if (aNumStr === bNumStr) {
                return 0;
            } else {
                return aNumStr < bNumStr ? -1 : 1;
            }
        } else {
            // lengths are not equal, then shorter string comes first
            return aNumStr.length - bNumStr.length;
        }
    }
    // loop while both strings have characters left
    while (aIndex < a.length && bIndex < b.length) {
        aChar = a.charAt(aIndex++);
        bChar = b.charAt(bIndex++);
        if (isDigit(aChar) && isDigit(bChar)) {
            result = compareNums();
            if (result !== 0) {
                return result;
            }
        } else {
            // not both numeric, just compare the characters themselves
            result = aChar.localeCompare(bChar);
            if (result !== 0) {
                return result;
            }
        }
    }
    // shorter one is first
    return (a.length - aIndex) - (b.length - bIndex);
}

array.sort(alphaNumCompare);
document.write(JSON.stringify(array).replace(/,/g, ", "));

The logic for this is as follows:

1. Implement a custom sort function for the Array sort() function.
2. Get next character in the string
3. If both are digits, then accumulate whatever sequence of consecutive digits there are.
4. Trim leading zeroes from the sequence of zeroes
5. If both sequences are only a sequence of zeroes, then the shorter one is less
6. The shorter sequence of numbers is less than the longer one
7. If both sequences of numbers are the same length, then you can just do a straight string compare on them to get the result
8. If both characters are not digits, then just compare them as a string
9. If strings have compared equal up to the point where one ends, then the shorter one is less

Answer 3

I suggest to use a kind of sort pattern for this special purpopse.

var data = ["E10N1", "E10N3", "E10N10", "E10N2", "E10N4", "E10N9", "E10N5", "E10N8", "E10N6", "E10N7"],
    result = data.map(function (el, i) {
        var a = /(\D*)(\d*)(\D*)(\d*)/i.exec(el);
        a.shift();
        return { index: i, value: a };
    }).sort(function (a, b) {
        var i = 0, r = 0;
        while (r === 0 && i < a.value.length && i < b.value.length) {
            r = i % 2 ? +a.value[i] - +b.value[i] : a.value[i].localeCompare(b.value[i]);
            i++;
        }
        return r;                
    }).map(function (el) {
        return data[el.index];
    });

document.write('<pre>' + JSON.stringify(result, 0, 4) + '</pre>');

Answer 4

In ASCII order 1 is less than 9 so "E10N10" is less than "E10N9". To get result you want, you need sorts the numbers in value order, while sorting the non-numbers in ASCII order. You can use this Alphanum Algorithm:

http://www.davekoelle.com/alphanum.html

Answer 5

You could use a regex to capture the digits at the end of each element and sort on those instead:

function sortStrings(a, b) {
    var regex = /E10N([\d]+)/;
    var apost = +a.match(regex)[1];
    var bpost = +b.match(regex)[1];
    if (apost < bpost) return -1;
    if (apost > bpost) return 1;
    return 0;
}

DEMO