Clasificación natural de elementos de matriz: cadenas con números

Este artículo profundiza en la tarea de ordenar matrices que contienen elementos que combinan cadenas y números en un orden natural, donde las secuencias numéricas dentro de las cadenas deben considerarse en el proceso de clasificación.

El Problema

Considere una matriz como esta:

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

Si intentamos ordenar esta matriz usando una función de clasificación convencional, podemos terminar con un orden incorrecto:

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

La solución: clasificación natural

Para lograr una clasificación natural, podemos aprovechar la siguiente función de JavaScript:

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

Esta función tokeniza las cadenas de entrada en matrices de valores numéricos y no numéricos. Luego compara las matrices lexicográficamente, teniendo en cuenta los valores numéricos como números enteros y los valores no numéricos como cadenas.

Ejemplo

Aplicar esta función a la matriz dada da como resultado el orden de clasificación natural deseado:

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

Esto produce la siguiente matriz ordenada:

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