Javascript: sorte naturelle de chaînes alphanumériques

Je recherche le moyen le plus simple de trier un tableau composé de nombres et de texte, et d'une combinaison de ceux-ci.

Par exemple

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

se transforme en

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

Cela va être utilisé en combinaison avec la solution à une autre question que j'ai posée ici .

La fonction de tri en elle-même fonctionne, ce dont j'ai besoin est une fonction qui peut dire que «19asd» est plus petit que «123asd».

J'écris ceci en JavaScript.

Edit: comme l' a souligné adormitu , ce que je recherche est une fonction de tri naturel

Ceci est désormais possible dans les navigateurs modernes utilisant localeCompare. En passant l' numeric: trueoption, il reconnaîtra intelligemment les nombres. Vous pouvez faire une utilisation insensible à la casse sensitivity: 'base'. Testé dans Chrome, Firefox et IE11.

Voici un exemple. Il revient 1, ce qui signifie que 10 va après 2:

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

Pour les performances lors du tri d'un grand nombre de chaînes, l'article dit:

Lors de la comparaison d'un grand nombre de chaînes, comme lors du tri de grands tableaux, il est préférable de créer un objet Intl.Collator et d'utiliser la fonction fournie par sa propriété compare. Lien vers les documents

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

Vous avez donc besoin d'une sorte naturelle ?

Si tel est le cas, ce scénario de Brian Huisman basé sur le travail de David Koelle serait peut-être ce dont vous avez besoin.

Il semble que la solution de Brian Huisman soit désormais directement hébergée sur le blog de David Koelle:

• Les solutions javascript de Brian Huisman
• L'article de David Koelle sur le sujet

Pour comparer les valeurs, vous pouvez utiliser une méthode de comparaison-

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

Mais pour accélérer le tri d'un tableau, configurez le tableau avant le tri, de sorte que vous ne devez effectuer les conversions en minuscules et l'expression régulière qu'une seule fois au lieu de chaque étape du tri.

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

Si vous avez un tableau d'objets, vous pouvez faire comme ceci:

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

La bibliothèque la plus complète pour gérer cela à partir de 2019 semble être d'ordre naturel .

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

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

const ordered = orderBy(unordered)

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

Il prend non seulement des tableaux de chaînes, mais peut également trier par la valeur d'une certaine clé dans un tableau d'objets. Il peut également identifier et trier automatiquement des chaînes de: devises, dates, devises et un tas d'autres choses.

Étonnamment, il ne représente que 1,6 Ko lorsqu'il est gzippé.

Imaginez une fonction de remplissage à 8 chiffres qui transforme:

• «123asd» -> «00000123asd»
• «19asd» -> «00000019asd»

Nous pouvons utiliser les chaînes remplies pour nous aider à trier «19asd» pour qu'il apparaisse avant «123asd».

Utilisez l'expression régulière /\d+/gpour trouver tous les nombres qui doivent être complétés:

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

Ce qui suit illustre le tri à l'aide de cette technique:

var list = [
    '123asd',
    '19asd',
    '12345asd',
    'asd123',
    'asd12'
];

function pad(n) { return ("00000000" + n).substr(-8); }
function natural_expand(a) { return a.replace(/\d+/g, pad) };
function natural_compare(a, b) {
    return natural_expand(a).localeCompare(natural_expand(b));
}

console.log(list.map(natural_expand).sort()); // intermediate values
console.log(list.sort(natural_compare)); // result

Les résultats intermédiaires montrent ce que fait la routine natural_expand () et vous donnent une compréhension du fonctionnement de la routine natural_compare suivante:

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

Les sorties:

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

En s'appuyant sur la réponse de @Adrien Be ci-dessus et en utilisant le code créé par Brian Huisman et David Koelle , voici un prototype modifié de tri pour un tableau d'objets:

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