Tri naturel de chaînes alphanumériques en JavaScript

Question

Je cherche le moyen le plus simple de trier un tableau composé de chiffres, de texte et d'une combinaison de ces éléments.

Par exemple,

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

se transforme en

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

Elle sera utilisée en combinaison avec la solution pour une autre question que j'ai posée ici .

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

J'écris ceci en JavaScript.

Je cherche une fonction pour le tri naturel.

Answer 1

Ceci est maintenant possible dans les navigateurs modernes en utilisant localeCompare . En passant le numeric: true il reconnaîtra intelligemment les nombres. Vous pouvez faire abstraction des majuscules et des minuscules en utilisant sensitivity: 'base' . Il a été testé dans Chrome, Firefox et Internet Explorer 11 .

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

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

Pour améliorer les performances lors du tri d'un grand nombre de chaînes de caractères, l'article dit :

Pour comparer un grand nombre de chaînes de caractères, par exemple pour trier 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.

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

Answer 2

Si vous avez un tableau d'objets, vous pouvez procéder comme suit :

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

Answer 3

Pour comparer des 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, il est préférable de trier le tableau avant de le trier, de sorte que vous n'ayez qu'à effectuer les conversions de minuscules et l'expression régulière une seule fois au lieu de le faire à 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];
    }
}

Answer 4

Vous avez donc besoin d'un tri naturel ?

Si c'est le cas, alors peut-être ce script de Brian Huisman basé sur le travail de David koelle serait ce qu'il vous faut.

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

• Les solutions javascript de Brian Huisman
• Article de David Koelle sur le sujet

Answer 5

Imaginez une fonction de mise à zéro des nombres n => n.padStart(8, "0") qui prend n'importe quel nombre et le remplit, c'est-à-dire

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

Cette fonction peut être utilisée pour aider à trier les "19" de manière à ce qu'elle apparaisse avant la chaîne de caractères "123" chaîne de caractères.

Ajoutons une expression rationnelle /\d+/g la création de la fonction d'expansion naturelle str => str.replace(/\d+/g, n => n.padStart(8, "0")) qui ne trouve que les sections numériques d'une chaîne et les remplit, c'est-à-dire

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

Nous pouvons maintenant utiliser cette fonction d'expansion naturelle pour mettre en œuvre le tri par ordre naturel :

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

Les résultats intermédiaires démontrés par list.map(ne).sort() montrent ce que le ne La fonction d'expansion naturelle le fait. Elle met en œuvre la mise à zéro des nombres uniquement sur les parties numériques de la chaîne et laisse les composants alphabétiques inchangés.

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

La version finale de la solution met en œuvre un comparateur d'ordre naturel nc mis en œuvre en tant que (a,b) => ne(a).localeCompare(ne(b)) et l'utilise dans list.sort(nc) afin que les choses soient ordonnées correctement :

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