Tipo natural de cadenas alfanuméricas en JavaScript

Estoy buscando la forma más fácil de ordenar una matriz que consta de números y texto, y una combinación de estos.

P.ej,

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

se convierte en

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

Esto se usará en combinación con la solución a otra pregunta que hice aquí.

La función de clasificación en sí misma funciona, lo que necesito es una función que pueda decir que ’19asd’ es más pequeño que ‘123asd’.

Estoy escribiendo esto en JavaScript.

Estoy buscando una función para la clasificación natural.

Esto ahora es posible en navegadores modernos usando localeCompare. Al pasar el numeric: true opción, reconocerá inteligentemente los números. Puede hacer que no se distinga entre mayúsculas y minúsculas usando sensitivity: 'base'. Probado en Chrome, Firefox e IE11.

Aquí hay un ejemplo. Vuelve 1lo que significa que 10 va después de 2:

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

Para el rendimiento al clasificar grandes cantidades de cadenas, el artículo dice:

Cuando se comparan grandes cantidades de cadenas, como al ordenar matrices grandes, es mejor crear un objeto Intl.Collator y usar la función proporcionada por su propiedad de comparación. Enlace de documentos

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

Si tiene una variedad de objetos, puede hacer esto:

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);

Para comparar valores, puede usar un método de comparación:

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

Pero para acelerar la clasificación de una matriz, arréglela antes de clasificarla, de modo que solo tenga que hacer conversiones de minúsculas y la expresión regular una vez en lugar de en cada paso de la clasificación.

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

Imagine una función de relleno de número cero n => n.padStart(8, "0") que toma cualquier número y lo rellena, es decir

• “19” -> “00000019”
• “123” -> “00000123”

Esta función se puede utilizar para ayudar a ordenar los "19" cadena para que aparezca antes de la "123" cuerda.

Agreguemos una expresión regular /\d+/g creando la función de expansión natural str => str.replace(/\d+/g, n => n.padStart(8, "0")) que encuentra solo secciones numéricas en una cadena y las rellena, es decir

• “19asd” -> “00000019asd”
• “123asd” -> “00000123asd”

Ahora, podemos usar esta función de expansión natural para ayudar a implementar la clasificación por orden natural:

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

Los resultados intermedios demostrados por list.map(ne).sort() mostrar lo que el ne la función de expansión natural sí lo hace. Implementa el relleno de números cero solo en las partes numéricas de la cadena y deja los componentes alfabéticos sin cambios.

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

La versión final de la solución implementa un comparador de orden natural. nc implementado como (a,b) => ne(a).localeCompare(ne(b)) y lo usa en list.sort(nc) para que las cosas se ordenen correctamente:

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

La biblioteca más completa para manejar esto a partir de 2019 parece ser orden natural por.

import { orderBy } from 'natural-orderby'

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

const ordered = orderBy(unordered)

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

No solo toma matrices de cadenas, sino que también puede ordenar por el valor de una determinada clave en una matriz de objetos. También puede identificar y ordenar automáticamente cadenas de: monedas, fechas, moneda y muchas otras cosas.

Sorprendentemente, también es solo 1.6kB cuando está comprimido con gzip.

Basándose en la respuesta anterior de @Adrien Be y usando el código que Brian Huismán & david koelle creado, aquí hay una clasificación prototipo modificada para una matriz de objetos:

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