Natural sort of alphanumerical strings in JavaScript

Question

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.

I'm looking for a function for natural sorting.

Xeric

see also How do you do string comparison in JavaScript? on #51665 – Questioning

The original question was asked in 2010, so it wouldn't be surprising :) – Xeric

Possible duplicate of How to sort strings in JavaScript – Haymes

@Haymes That's not a natural sort – Portfire

Answer 1

This is now possible in modern browsers using localeCompare. By passing the numeric: true option, it will smartly recognize numbers. You can do case-insensitive using sensitivity: 'base'. It was tested in Chrome, Firefox, and Internet Explorer 11.

Here's an example. It returns 1, meaning 10 goes after 2:

'10'.localeCompare('2', undefined, {numeric: true, sensitivity: 'base'})

For performance when sorting large numbers of strings, the article says:

When comparing large numbers of strings, such as in sorting large arrays, it is better to create an Intl.Collator object and use the function provided by its compare property.

var collator = new Intl.Collator(undefined, {numeric: true, sensitivity: 'base'});
var myArray = ['1_Document', '11_Document', '2_Document'];
console.log(myArray.sort(collator.compare));

Dudden

If you want to sort an array of objects, you can also use the Collator: codepen.io/TimPietrusky/pen/rKzoGN – Jillian

To clarify above comment: "If the locales argument is not provided or is undefined, the runtime's default locale is used." – Vacua

@Dudden Here what is undefined parameter here..what is the purpose? – Seurat

@Seurat we're passing undefined to avoid having to specify a locale, it will use the browser's default locale. – Dudden

If you'll add '01_Document' to your array, it will be placed after '1_Document'. This is wrong. How can we handle that? – Quixotism

@Quixotism In Chrome I'm seeing that numbers with leading 0's are considered equivalent to regular numbers, and are left in their original order if they're equal, which seems like correct behavior to me. – Dudden

I don't know what you've checked in Chrome but here is an example from typescript playground you can see... typescriptlang.org/play?#code/… – Quixotism

@Quixotism I looked at your playground, but it's working like I would expect. I see it outputting ["1_Document", "01_Document", "2_Document", "11_Document"]. The first two documents "1" and "01" are considered equivalent, so they stay in their same order from the input. If you swap them in the input, the output will also be swapped. This is expected behavior from what's called a "stable sort", where if 2 items are equivalent, they stay in the same order. – Dudden

Answer 2

If you have an array of objects, you can do it like this:

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

var myArrayObjects = [{
    "id": 1,
    "name": "1 example"
  },
  {
    "id": 2,
    "name": "100 example"
  },
  {
    "id": 3,
    "name": "12 example"
  },
  {
    "id": 4,
    "name": "5 example"
  },

]

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

Boll

Answer 3

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];
    }
}

Uralaltaic

would this work in my case, with the inner array deciding the order of the outer one? – Xeric

What's String.prototype.tlc()? Is this your own code or did you get it from somewhere? If the latter, please link to the page. – Birthday

sorry about the mistake- corrected, thank you. If you want a[1] and b[1] to control the sort, use a= String(a[1]).toLowerCase(); b= String(b[1]).toLowerCase(); – Uralaltaic

I just had a list of data that I wanted to sort, thought it should be easy to do in Chrome Dev Tools console - thanks for the function! – Consumption

Answer 4

Imagine a number-zero-padding function n => n.padStart(8, "0") that takes any number and pads it, i.e.

• "19" -> "00000019"
• "123" -> "00000123"

This function can be used to help sort the "19" string so that it appears before the "123" string.

Let's add a regex /\d+/g creating the natural expansion function str => str.replace(/\d+/g, n => n.padStart(8, "0")) which finds only number sections in a string and pads them, i.e.

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

Now, we can use this natural expansion function to help implement natural order sort:

const list = [
    "123asd",
    "19asd",
    "12345asd",
    "asd123",
    "asd12"
];

const ne = str => str.replace(/\d+/g, n => n.padStart(8, "0"));
const nc = (a,b) => ne(a).localeCompare(ne(b));

console.log(list.map(ne).sort()); // intermediate values
console.log(list.sort(nc)); // result

The intermediate results demonstrated by list.map(ne).sort() show what the ne natural expansion function does. It implements number-zero-padding on only the number portions of the string and leaves the alphabet components unchanged.

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

The final version of solution implements a natural order comparator nc implemented as (a,b) => ne(a).localeCompare(ne(b)) and uses it in list.sort(nc) so things get ordered correctly:

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

Retaretable

Answer 5

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

import { orderBy } from '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 it can also 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.6 kB when gzipped.

Wharton

Whilst not explicitly stated, your answer appears to be specific to Node.JS. – Retaretable

@StephenQuan Thanks- I update the answer to use ES6 module syntax which is less NodeJS specific. – Wharton

Answer 6

Building on kennebec's answer 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"];
  }
}

Annadiane

What are the magic numbers 46, 48, and 57? – Effective

Answer 7

I needed to sort an array of objects by multiple fields. After reading a bunch on the topic and some time working with various solutions; I ended up with something I didn't quite see anywhere all in one piece, so figured I'd share it here incase it helps anyone:

const orderBy = orders => (a, b) => {
    const sortDirection = { asc: 1, desc: -1 };
    const sortCollator = new Intl.Collator(undefined, { numeric: true, sensitivity: 'base' });
    const totalOrders = orders.length;

    for (let index = 0; index < totalOrders; index++) {
        const { property, direction = 'desc' } = orders[index];
        const directionInt = sortDirection[direction];
        const compare = sortCollator.compare(a[property], b[property]);

        if (compare < 0) return directionInt;
        if (compare > 0) return -directionInt;
    }

    return 0;
};

// Example:

const unsorted = [
    { name: 'Bananas', count: 1 },
    { name: 'Apples', count: 3 },
    { name: 'Bananas', count: 3 },
    { name: 'bananas', count: 2 },
];

const sorted = unsorted.sort(orderBy([{ property: 'name' }, { property: 'count', direction: 'asc' }]));

console.log(sorted);

Eisenstark

Nice stuff; works for me! Concerns is: Does it work with numbers (actual and string) as expected? Many past solutions have comments talking about number sorting. Also, would be nice to see a typescript version. – Normannormand