Tri de nombres mélangés et de chaînes

Question

J'ai une liste de chaînes pouvant contenir une lettre ou une représentation sous forme de chaîne d'un int (2 chiffres maximum). Ils doivent être triés par ordre alphabétique ou (quand il s’agit bien d’un entier) sur la valeur numérique qu’il représente.

Exemple:

IList<string> input = new List<string>()
    {"a", 1.ToString(), 2.ToString(), "b", 10.ToString()};

input.OrderBy(s=>s)
  // 1
  // 10
  // 2
  // a
  // b

Ce que je voudrais, c'est

  // 1
  // 2
  // 10
  // a
  // b

J'ai une idée du formatage avec essayer de l’analyser, puis si c’est une tryparse réussie, formatez-la avec mon propre formatage de chaîne personnalisé pour lui donner des zéros précédents. J'espère quelque chose de plus simple et performant.

Modifier
J'ai fini par créer un IComparer que j'ai vidé dans ma bibliothèque Utils pour une utilisation ultérieure.
Pendant que j’y étais, j’ai jeté des doubles dans le mélange aussi.

public class MixedNumbersAndStringsComparer : IComparer<string> {
    public int Compare(string x, string y) {
        double xVal, yVal;

        if(double.TryParse(x, out xVal) && double.TryParse(y, out yVal))
            return xVal.CompareTo(yVal);
        else 
            return string.Compare(x, y);
    }
}

//Tested on int vs int, double vs double, int vs double, string vs int, string vs doubl, string vs string.
//Not gonna put those here
[TestMethod]
public void RealWorldTest()
{
    List<string> input = new List<string>() { "a", "1", "2,0", "b", "10" };
    List<string> expected = new List<string>() { "1", "2,0", "10", "a", "b" };
    input.Sort(new MixedNumbersAndStringsComparer());
    CollectionAssert.AreEquivalent(expected, input);
}

Answer 1

Vous pourriez peut-être utiliser une approche plus générique et utiliser un naturel trier un algorithme tel que l'implémentation C #, ici .

Answer 2

Deux manières me viennent à l’esprit, sans savoir laquelle est la plus performante. Implémenter un IComparer personnalisé:

class MyComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int xVal, yVal;
        var xIsVal = int.TryParse( x, out xVal );
        var yIsVal = int.TryParse( y, out yVal );

        if (xIsVal && yIsVal)   // both are numbers...
            return xVal.CompareTo(yVal);
        if (!xIsVal && !yIsVal) // both are strings...
            return x.CompareTo(y);
        if (xIsVal)             // x is a number, sort first
            return -1;
        return 1;               // x is a string, sort last
    }
}

var input = new[] {"a", "1", "10", "b", "2", "c"};
var e = input.OrderBy( s => s, new MyComparer() );

Ou divisez la séquence en nombres et en non-nombres, puis triez chaque sous-groupe, puis joignez les résultats triés; quelque chose comme:

var input = new[] {"a", "1", "10", "b", "2", "c"};

var result = input.Where( s => s.All( x => char.IsDigit( x ) ) )
                  .OrderBy( r => { int z; int.TryParse( r, out z ); return z; } )
                  .Union( input.Where( m => m.Any( x => !char.IsDigit( x ) ) )
                               .OrderBy( q => q ) );

Answer 3

Utilisez l'autre surcharge de OrderBy qui prend un paramètre IComparer .

Vous pouvez ensuite implémenter votre propre IComparer qui utilise int.TryParse pour indiquer s'il s'agit d'un nombre ou non.

Answer 4

Je dirais que vous pouvez séparer les valeurs à l'aide d'une expression régulière (en supposant que tout est un entier), puis les rejoindre ensemble.

//create two lists to start
string[] data = //whatever...
List<int> numbers = new List<int>();
List<string> words = new List<string>();

//check each value
foreach (string item in data) {
    if (Regex.IsMatch("^\d+<*>quot;, item)) {
        numbers.Add(int.Parse(item));
    }
    else {
        words.Add(item);
    }
}

Ensuite, avec vos deux listes, vous pouvez trier chacune d’elles puis les fusionner dans le format de votre choix.

Answer 5

Vous pouvez simplement utiliser la fonction fournie par l'API Win32 :

[DllImport ("shlwapi.dll", CharSet=CharSet.Unicode, ExactSpelling=true)]
static extern int StrCmpLogicalW (String x, String y);

et appelez-le depuis un IComparer comme d'autres l'ont montré.

Answer 6

public static int? TryParse(string s)
{
    int i;
    return int.TryParse(s, out i) ? (int?)i : null;
}

// in your method
IEnumerable<string> input = new string[] {"a", "1","2", "b", "10"};
var list = input.Select(s => new { IntVal = TryParse(s), String =s}).ToList();
list.Sort((s1, s2) => {
    if(s1.IntVal == null && s2.IntVal == null)
    {
        return s1.String.CompareTo(s2.String);
    }
    if(s1.IntVal == null)
    {
        return 1;
    }
    if(s2.IntVal == null)
    {
        return -1;
    }
    return s1.IntVal.Value.CompareTo(s2.IntVal.Value);
});
input = list.Select(s => s.String);

foreach(var x in input)
{
    Console.WriteLine(x);
}

La conversion est toujours effectuée, mais une seule fois par élément.

Answer 7

Vous pouvez utiliser un comparateur personnalisé - l'instruction de commande serait alors:

var result = input.OrderBy(s => s, new MyComparer());

où MyComparer est défini comme suit:

public class MyComparer : Comparer<string>
{
    public override int Compare(string x, string y)
    {

        int xNumber;
        int yNumber;
        var xIsNumber = int.TryParse(x, out xNumber);
        var yIsNumber = int.TryParse(y, out yNumber);

        if (xIsNumber && yIsNumber)
        {
            return xNumber.CompareTo(yNumber);
        }
        if (xIsNumber)
        {
            return -1;
        }
        if (yIsNumber)
        {
            return 1;
        }
        return x.CompareTo(y);
    }
}

Bien que cela puisse sembler un peu prolixe, il encapsule la logique de tri dans un type approprié. Vous pouvez ensuite, si vous le souhaitez, facilement soumettre la comparaison à des tests automatisés (tests unitaires). Il est également réutilisable.

(Il est peut-être possible de rendre l'algorithme un peu plus clair, mais c'était le mieux que je pouvais rapidement jeter ensemble.)

Answer 8

Vous pouvez également "tricher". en quelques sortes. Selon votre description du problème, vous savez que toute chaîne de longueur 2 sera un nombre. Donc, il suffit de trier toutes les chaînes de longueur 1. Et ensuite, de trier toutes les chaînes de longueur 2. Et ensuite, effectuez une série de permutations pour réorganiser vos chaînes dans le bon ordre. Le processus fonctionnera essentiellement comme suit: (en supposant que vos données se trouvent dans un tableau.)

Étape 1: Poussez toutes les chaînes de longueur 2 à la fin du tableau. Gardez une trace de votre nombre.

Étape 2: triez sur place les chaînes de longueur 1 et de longueur 2.

Étape 3: recherche binaire de 'a' qui se situerait à la limite de vos deux moitiés.

Étape 4: Échangez vos chaînes de deux chiffres avec les lettres si nécessaire.

Cela dit, bien que cette approche fonctionne, ne comporte pas d'expressions régulières et n'essaie pas d'analyser les valeurs non-int en tant qu'int - je ne le recommande pas. Vous allez écrire beaucoup plus de code que les autres approches déjà suggérées. Cela brouille le sens de ce que vous essayez de faire. Cela ne fonctionne pas si vous obtenez soudainement des chaînes de deux lettres ou des chaînes de trois chiffres. Etc. Je ne fais que l'inclure pour montrer comment on peut aborder les problèmes différemment et proposer des solutions alternatives.

Answer 9

Utilisez une transformation de Schwartzian pour effectuer des conversions en O (n)!

private class Normalized : IComparable<Normalized> {
  private readonly string str;
  private readonly int val;

  public Normalized(string s) {
    str = s;

    val = 0;
    foreach (char c in s) {
      val *= 10;

      if (c >= '0' && c <= '9')
        val += c - '0';
      else
        val += 100 + c;
    }
  }

  public String Value { get { return str; } }

  public int CompareTo(Normalized n) { return val.CompareTo(n.val); }
};

private static Normalized In(string s) { return new Normalized(s); }
private static String Out(Normalized n) { return n.Value; }

public static IList<String> MixedSort(List<String> l) {
  var tmp = l.ConvertAll(new Converter<String,Normalized>(In));
  tmp.Sort();
  return tmp.ConvertAll(new Converter<Normalized,String>(Out));
}

Answer 10

J'ai eu un problème similaire et j'ai atterri ici: trier les chaînes avec un suffixe numérique comme dans l'exemple suivant.

Original:

"Test2", "Test1", "Test10", "Test3", "Test20"

Résultat du tri par défaut:

"Test1", "Test10", "Test2", "Test20", "Test3"

Résultat de tri souhaité:

"Test1", "Test2", "Test3, "Test10", "Test20"

J'ai fini par utiliser une liste de comparaison personnalisée:

public class NaturalComparer : IComparer
{

    public NaturalComparer()
    {
        _regex = new Regex("\\d+<*>quot;, RegexOptions.IgnoreCase);
    }

    private Regex _regex;

    private string matchEvaluator(System.Text.RegularExpressions.Match m)
    {
        return Convert.ToInt32(m.Value).ToString("D10");
    }

    public int Compare(object x, object y)
    {
        x = _regex.Replace(x.ToString, matchEvaluator);
        y = _regex.Replace(y.ToString, matchEvaluator);

        return x.CompareTo(y);
    }
}   

HTH; o)