Categories
javascript jquery sorting

Sort Array Elements (string with numbers), natural sort

57

I have an array like;

["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"]

And need to sort it so it appears like;

["IL0 Foo", "IL3 Bob says hello", "IL10 Baz", "PI0 Bar"]

I have tried a sort function;

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

but this gives the order

["IL0 Foo", "IL10 Baz", "IL3 Bob says hello", "PI0 Bar"]

I have tried to think of a regex that will work but can’t get my head around it.
If it helps the format will always be 2 letters, x amount of numbers, then any number of characters.

9

  • Letter first, then number?

    Mar 18, 2013 at 14:16


  • @BradChristie, yes sort by first two letters then the numbers, the others characters not required (but would be nice)

    – Rooneyl

    Mar 18, 2013 at 14:17


  • So if you had IL10 Hello & IL10 Bob, which comes first?

    Mar 18, 2013 at 14:18

  • in an ideal world IL10 Bob

    – Rooneyl

    Mar 18, 2013 at 14:19

  • 1

    @RyanGates Except this isn’t an alphabetical ordering and has nothing to do with elements in the DOM.

    Mar 18, 2013 at 14:23

112

This is called “natural sort” and can be implemented in JS like this:

function naturalCompare(a, b) {
    var ax = [], bx = [];

    a.replace(/(\d+)|(\D+)/g, function(_, $1, $2) { ax.push([$1 || Infinity, $2 || ""]) });
    b.replace(/(\d+)|(\D+)/g, function(_, $1, $2) { bx.push([$1 || Infinity, $2 || ""]) });
    
    while(ax.length && bx.length) {
        var an = ax.shift();
        var bn = bx.shift();
        var nn = (an[0] - bn[0]) || an[1].localeCompare(bn[1]);
        if(nn) return nn;
    }

    return ax.length - bx.length;
}

/////////////////////////

test = [
    "img12.png",
    "img10.png",
    "img2.png",
    "img1.png",
    "img101.png",
    "img101a.png",
    "abc10.jpg",
    "abc10",
    "abc2.jpg",
    "20.jpg",
    "20",
    "abc",
    "abc2",
    ""
];

test.sort(naturalCompare)
document.write("<pre>" + JSON.stringify(test,0,3));

To sort in reverse order, just swap the arguments:

test.sort(function(a, b) { return naturalCompare(b, a) })

or simply

test = test.sort(naturalCompare).reverse();

6

  • 1

    Seems to favor strings that start with alphabetical characters over numeric characters. Fixed by replacing $1 || 0 with typeof($1) == 'undefined' ? Infinity : $1

    – colllin

    May 4, 2014 at 7:30


  • 2

    Could anyone help how this can be implemented for both ascending and descending sorting of array ?

    – anusreemn

    Mar 18, 2015 at 11:51

  • Please note the .reverse will iterate the array again.

    Feb 23, 2017 at 2:34

  • Can someone explain with some detial exactly what is happening with the regex replaces / Infinity? Then the while loop with shift mechanisms? I don’t fully understand what is happening there

    – DRobertE

    Mar 27, 2018 at 14:06

  • I just wanted to ask, for time-space complexity/Big O, this would be O(n) right?

    Oct 17, 2021 at 19:46

22

You could use String#localeCompare with options

sensitivity

Which differences in the strings should lead to non-zero result values. Possible values are:

  • "base": Only strings that differ in base letters compare as unequal. Examples: a ≠ b, a = á, a = A.
  • "accent": Only strings that differ in base letters or accents and other diacritic marks compare as unequal. Examples: a ≠ b, a ≠ á, a = A.
  • "case": Only strings that differ in base letters or case compare as unequal. Examples: a ≠ b, a = á, a ≠ A.
  • "variant": Strings that differ in base letters, accents and other diacritic marks, or case compare as unequal. Other differences may also be taken into consideration. Examples: a ≠ b, a ≠ á, a ≠ A.

The default is “variant” for usage “sort”; it’s locale dependent for usage “search”.

numeric

Whether numeric collation should be used, such that “1” < “2” < “10”. Possible values are true and false; the default is false. This option can be set through an options property or through a Unicode extension key; if both are provided, the options property takes precedence. Implementations are not required to support this property.

var array = ["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"];

array.sort(function (a,b) {
    return a.localeCompare(b, undefined, { numeric: true, sensitivity: 'base' });
});

console.log(array);

2

  • Will it work if array contains undefined or null values? I guess it will just ignore it instead of placing them at the front or end depending on type of sort

    – Umang

    Apr 26 at 3:35

  • 1

    @Umang, unfortunately localeCompare works only for strings. the parameter is converted to string.

    Apr 26 at 7:36


5

var re = /([a-z]+)(\d+)(.+)/i;
var arr = ["IL0 Foo", "PI0 Bar", "IL10 Baz", "IL3 Bob says hello"];
var order = arr.sort( function(a,b){
    var ma = a.match(re),
        mb = b.match(re),
        a_str = ma[1],
        b_str = mb[1],
        a_num = parseInt(ma[2],10),
        b_num = parseInt(mb[2],10),
        a_rem = ma[3],
        b_rem = mb[3];
    return a_str > b_str ? 1 : a_str < b_str ? -1 : a_num > b_num ? 1 : a_num < b_num ? -1 : a_rem > b_rem;  
});