Tri des chaînes contenant des nombres d'une manière conviviale

Question

Étant habitué à la manière standard de trier les chaînes, j'ai été surpris quand j'ai remarqué que Windows trie les fichiers par leur nom d'une manière avancée. Permettez-moi de vous donner un exemple:

track1.mp3
Track2.mp3
Track10.mp3
Track20.mp3

Je pense que ces noms sont comparés (lors du tri) en fonction des lettres et par numéros séparément.

D'autre part, ce qui suit est la même liste triée de façon standard:
track1.mp3
Track10.mp3
Track2.mp3
Track20.mp3

Je voudrais créer un alogorithme de comparaison dans Delphi qui me permettrait de trier les chaînes de la même manière. Au début, je pensais qu'il suffirait de comparer les caractères consécutifs de deux chaînes pendant qu'elles sont des lettres. Quand un chiffre serait trouvé à une certaine position des deux chaînes, je lirais tous les chiffres qui les suivent pour former un nombre et ensuite comparer les nombres.

Pour vous donner un exemple, je vais comparer les chaînes « Track10 » et « FTrack2 » de cette façon:
1) lire les caractères alors qu'ils sont égaux et alors qu'ils sont des lettres: « Track », « Track »
2) si un chiffre est trouvé, lire tous les chiffres suivants: "10", "2"
2a) s'ils sont égaux, aller à 1 ou terminer
Dix est supérieur à deux, donc "Track10" est supérieur à "Track2"

Il semblait que tout irait bien jusqu'à ce que je remarque, lors de mes tests, que Windows a considéré "Track010" plus bas que "Track10", alors que je pensais que le premier était g plus longue (sans mentionner que selon mon algorithme, les deux chaînes seraient égales, ce qui est faux). Pourriez-vous me donner une idée de la manière dont Windows trie les fichiers par nom ou peut-être avez-vous un algorithme prêt à l'emploi (dans n'importe quel langage de programmation) sur lequel je pourrais me baser?

Merci beaucoup!
Mariusz

Answer 1

Jeff a rédigé un article à ce sujet sur Coding Horror. Ceci est appelé natural sorting, où vous traitez efficacement un groupe de chiffres comme un "caractère" unique. Il existe des implémentations dans toutes les langues sous le soleil, mais bizarrement, il n'est généralement pas intégré dans les bibliothèques standard de la plupart des langages.

Answer 2

Ceci est aussi un bon article à ce sujet. Vraiment expose comment encapsule toute la logique dans le comparateur: http://www.codeproject.com/KB/string/NaturalSortComparer.aspx

Answer 3

La mère de toutes sortes:

ls '*.mp3' | sort --version-sort

Answer 4

La meilleure façon absolue, j'ai trouvé, était d'isoler la chaîne que vous voulez, alors dans le cas de l'OP, Path.GetFileNameWithoutExtension(), supprime les non-chiffres, convertit en int, et trie. En utilisant LINQ et certaines méthodes d'extension, c'est un one-liner.Dans mon cas, je vais sur les répertoires:

Directory.GetDirectories(@"a:\b\c").OrderBy(x => x.RemoveNonDigits().ToIntOrZero()) 

Où RemoveNonDigits et ToIntOrZero sont des méthodes d'extensions:

public static string RemoveNonDigits(this string value) { 
    return Regex.Replace(value, "[^0-9]", string.Empty); 
} 

public static int ToIntOrZero(this string toConvert) { 
    try { 
     if (toConvert == null || toConvert.Trim() == string.Empty) return 0;    
     return int.Parse(toConvert); 
    } catch (Exception) { 
     return 0; 
    } 
} 

Les méthodes d'extension sont des outils communs que j'utilise partout. YMMV.