Ordenar números y cadenas mixtos

Question

Tengo una lista de cadenas que pueden contener una letra o una representación de cadena de un int (máximo 2 dígitos). Deben ordenarse alfabéticamente o (cuando en realidad es un int) según el valor numérico que representa.

Ejemplo:

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

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

Lo que me gustaría es

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

Tengo una idea que implica formatearlo con el intento de analizarlo, luego, si es un intento exitoso de formatearlo con mi propio formateador de cadena personalizado para que tenga ceros anteriores. Espero algo más simple y eficaz.

Editar
Terminé haciendo un IComparer que descargué en mi biblioteca de Utils para su uso posterior.
Mientras estaba en eso, también agregué dobles en la mezcla.

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

Quizás podría optar por un enfoque más genérico y utilizar un natural algoritmo de clasificación como la implementación de C # aquí .

Answer 2

Se te ocurren dos maneras, no estoy seguro de cuál es más eficiente. Implemente un IComparer personalizado:

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

O, divida la secuencia en números y no números, luego ordene cada subgrupo y, finalmente, combine los resultados ordenados; algo como:

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

Utilice la otra sobrecarga de OrderBy que toma un parámetro IComparer .

Luego puede implementar su propio IComparer que usa int. TryParse para saber si es un número o no.

Answer 4

Diría que podría dividir los valores utilizando una expresión regular (suponiendo que todo sea un int) y luego volver a unirlos.

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

Luego, con sus dos listas, puede ordenar cada una de ellas y luego fusionarlas nuevamente en el formato que desee.

Answer 5

Podría usar la función proporcionada por la API de Win32 :

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

y llámelo desde un IComparer como lo han mostrado otros.

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

Todavía realiza la conversión, pero solo una vez / elemento.

Answer 7

Podría usar un comparador personalizado; la declaración de pedido sería:

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

donde MyComparer se define así:

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

Aunque esto puede parecer un poco detallado, encapsula la lógica de clasificación en un tipo adecuado. Luego, si lo desea, puede someter fácilmente al Comparer a pruebas automatizadas (pruebas unitarias). También es reutilizable.

(Puede ser posible que el algoritmo sea un poco más claro, pero esto fue lo mejor que pude juntar rápidamente).

Answer 8

También podrías '' engañar '' en algún sentido. Según su descripción del problema, sabe que cualquier cadena de longitud 2 será un número. Entonces, solo clasifique todas las cadenas de longitud 1. Y luego ordene todas las cadenas de longitud 2. Y luego intercambie un montón para reordenar sus cadenas en el orden correcto. Esencialmente, el proceso funcionará de la siguiente manera: (suponiendo que sus datos estén en una matriz).

Paso 1: Empuje todas las cadenas de longitud 2 hasta el final de la matriz. Hacer un seguimiento de cuántos tiene.

Paso 2: en su lugar, clasifique las cadenas de longitud 1 y las cadenas de longitud 2.

Paso 3: Búsqueda binaria de 'a' que estaría en el límite de sus dos mitades.

Paso 4: Cambie sus cadenas de dos dígitos con las letras según sea necesario.

Dicho esto, si bien este enfoque funcionará, no implica expresiones regulares y no intenta analizar valores no int como int; no lo recomiendo. Estará escribiendo significativamente más código que otros enfoques ya sugeridos. Se ofusca el punto de lo que estás tratando de hacer. No funciona si de repente obtienes cadenas de dos letras o cadenas de tres dígitos. Etc. Solo lo incluyo para mostrar cómo puede ver los problemas de manera diferente y encontrar soluciones alternativas.

Answer 9

¡Utilice una Schwartzian Transform para realizar conversiones 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

Tuve un problema similar y aterricé aquí: ordenando cadenas que tienen un sufijo numérico como en el siguiente ejemplo.

Original:

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

Resultado de ordenación predeterminado:

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

Resultado de ordenación deseado:

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

Terminé usando un Comparer personalizado:

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)