Tri naturel des éléments de tableau : chaînes avec des nombres

Cet article approfondit la tâche de tri des tableaux contenant des éléments qui combinent des chaînes et des nombres dans un ordre naturel, où les séquences numériques dans les chaînes doivent être prises en compte dans le processus de tri.

Le Problème

Considérons un tableau comme celui-ci :

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

Si nous essayons de trier ce tableau à l'aide d'une fonction de tri conventionnelle, nous pouvons nous retrouver avec un ordre incorrect :

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

La solution : le tri naturel

Pour réaliser un tri naturel, nous pouvons exploiter la fonction JavaScript suivante :

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

Cette fonction tokenise les chaînes d'entrée en tableaux de valeurs numériques et non numériques. Il compare ensuite les tableaux lexicographiquement, en prenant en compte les valeurs numériques sous forme d'entiers et les valeurs non numériques sous forme de chaînes.

Exemple

Application de cette fonction au tableau donné donne l'ordre de tri naturel souhaité :

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

Cela produit le tableau trié suivant :

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