[javascript] Javascript : natural sort of alphanumerical strings

I'm looking for the easiest way to sort an array that consists of numbers and text, and a combination of these.

E.g.

'123asd'
'19asd'
'12345asd'
'asd123'
'asd12'

turns into

'19asd'
'123asd'
'12345asd'
'asd12'
'asd123'

This is going to be used in combination with the solution to another question I've asked here.

The sorting function in itself works, what I need is a function that can say that that '19asd' is smaller than '123asd'.

I'm writing this in JavaScript.

Edit: as adormitu pointed out, what I'm looking for is a function for natural sorting

So you need a natural sort ?

If so, than maybe this script by Brian Huisman based on David koelle's work would be what you need.

It seems like Brian Huisman's solution is now directly hosted on David Koelle's blog:

• Brian Huisman's javascript solutions
• David koelle's article on the subject

Building on @Adrien Be's answer above and using the code that Brian Huisman & David koelle created, here is a modified prototype sorting for an array of objects:

//Usage: unsortedArrayOfObjects.alphaNumObjectSort("name");
//Test Case: var unsortedArrayOfObjects = [{name: "a1"}, {name: "a2"}, {name: "a3"}, {name: "a10"}, {name: "a5"}, {name: "a13"}, {name: "a20"}, {name: "a8"}, {name: "8b7uaf5q11"}];
//Sorted: [{name: "8b7uaf5q11"}, {name: "a1"}, {name: "a2"}, {name: "a3"}, {name: "a5"}, {name: "a8"}, {name: "a10"}, {name: "a13"}, {name: "a20"}]

// **Sorts in place**
Array.prototype.alphaNumObjectSort = function(attribute, caseInsensitive) {
  for (var z = 0, t; t = this[z]; z++) {
    this[z].sortArray = new Array();
    var x = 0, y = -1, n = 0, i, j;

    while (i = (j = t[attribute].charAt(x++)).charCodeAt(0)) {
      var m = (i == 46 || (i >=48 && i <= 57));
      if (m !== n) {
        this[z].sortArray[++y] = "";
        n = m;
      }
      this[z].sortArray[y] += j;
    }
  }

  this.sort(function(a, b) {
    for (var x = 0, aa, bb; (aa = a.sortArray[x]) && (bb = b.sortArray[x]); x++) {
      if (caseInsensitive) {
        aa = aa.toLowerCase();
        bb = bb.toLowerCase();
      }
      if (aa !== bb) {
        var c = Number(aa), d = Number(bb);
        if (c == aa && d == bb) {
          return c - d;
        } else {
          return (aa > bb) ? 1 : -1;
        }
      }
    }

    return a.sortArray.length - b.sortArray.length;
  });

  for (var z = 0; z < this.length; z++) {
    // Here we're deleting the unused "sortArray" instead of joining the string parts
    delete this[z]["sortArray"];
  }
}

To compare values you can use a comparing method-

function naturalSorter(as, bs){
    var a, b, a1, b1, i= 0, n, L,
    rx=/(\.\d+)|(\d+(\.\d+)?)|([^\d.]+)|(\.\D+)|(\.$)/g;
    if(as=== bs) return 0;
    a= as.toLowerCase().match(rx);
    b= bs.toLowerCase().match(rx);
    L= a.length;
    while(i<L){
        if(!b[i]) return 1;
        a1= a[i],
        b1= b[i++];
        if(a1!== b1){
            n= a1-b1;
            if(!isNaN(n)) return n;
            return a1>b1? 1:-1;
        }
    }
    return b[i]? -1:0;
}

But for speed in sorting an array, rig the array before sorting, so you only have to do lower case conversions and the regular expression once instead of in every step through the sort.

function naturalSort(ar, index){
    var L= ar.length, i, who, next, 
    isi= typeof index== 'number', 
    rx=  /(\.\d+)|(\d+(\.\d+)?)|([^\d.]+)|(\.(\D+|$))/g;
    function nSort(aa, bb){
        var a= aa[0], b= bb[0], a1, b1, i= 0, n, L= a.length;
        while(i<L){
            if(!b[i]) return 1;
            a1= a[i];
            b1= b[i++];
            if(a1!== b1){
                n= a1-b1;
                if(!isNaN(n)) return n;
                return a1>b1? 1: -1;
            }
        }
        return b[i]!= undefined? -1: 0;
    }
    for(i= 0; i<L; i++){
        who= ar[i];
        next= isi? ar[i][index] || '': who;
        ar[i]= [String(next).toLowerCase().match(rx), who];
    }
    ar.sort(nSort);
    for(i= 0; i<L; i++){
        ar[i]= ar[i][1];
    }
}

The most fully-featured library to handle this as of 2019 seems to be natural-orderby.

const { orderBy } = require('natural-orderby')

const unordered = [
  '123asd',
  '19asd',
  '12345asd',
  'asd123',
  'asd12'
]

const ordered = orderBy(unordered)

// [ '19asd',
//   '123asd',
//   '12345asd',
//   'asd12',
//   'asd123' ]

It not only takes arrays of strings, but also can sort by the value of a certain key in an array of objects. It can also automatically identify and sort strings of: currencies, dates, currency, and a bunch of other things.

Surprisingly, it's also only 1.6kB when gzipped.

Imagine an 8 digit padding function that transforms:

• '123asd' -> '00000123asd'
• '19asd' -> '00000019asd'

We can used the padded strings to help us sort '19asd' to appear before '123asd'.

Use the regular expression /\d+/g to help find all the numbers that need to be padded:

str.replace(/\d+/g, pad)

The following demonstrates sorting using this technique:

var list = [_x000D_
    '123asd',_x000D_
    '19asd',_x000D_
    '12345asd',_x000D_
    'asd123',_x000D_
    'asd12'_x000D_
];_x000D_
_x000D_
function pad(n) { return ("00000000" + n).substr(-8); }_x000D_
function natural_expand(a) { return a.replace(/\d+/g, pad) };_x000D_
function natural_compare(a, b) {_x000D_
    return natural_expand(a).localeCompare(natural_expand(b));_x000D_
}_x000D_
_x000D_
console.log(list.map(natural_expand).sort()); // intermediate values_x000D_
console.log(list.sort(natural_compare)); // result

The intermediate results show what the natural_expand() routine does and gives you an understanding of how the subsequent natural_compare routine will work:

[
  "00000019asd",
  "00000123asd",
  "00012345asd",
  "asd00000012",
  "asd00000123"
]

Outputs:

[
  "19asd",
  "123asd",
  "12345asd",
  "asd12",
  "asd123"
]

If you have a array of objects you can do like this:

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

var myArrayObjects = [{_x000D_
    "id": 1,_x000D_
    "name": "1 example"_x000D_
  },_x000D_
  {_x000D_
    "id": 2,_x000D_
    "name": "100 example"_x000D_
  },_x000D_
  {_x000D_
    "id": 3,_x000D_
    "name": "12 example"_x000D_
  },_x000D_
  {_x000D_
    "id": 4,_x000D_
    "name": "5 example"_x000D_
  },_x000D_
_x000D_
]_x000D_
_x000D_
myArrayObjects = myArrayObjects.sort(function(a, b) {_x000D_
  return a.name.localeCompare(b.name, undefined, {_x000D_
    numeric: true,_x000D_
    sensitivity: 'base'_x000D_
  });_x000D_
});_x000D_
console.log(myArrayObjects);