Triagem números mistos e cordas

Question

Eu tenho uma lista de strings que podem conter uma letra ou uma representação de um int (máximo 2 dígitos). Eles precisam ser ordenado por ordem alfabética ou (quando na verdade é um int) sobre o valor numérico que representa.

Exemplo:

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

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

O que eu quero é

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

Eu tenho uma idéia envolvendo formatá-lo com a tentativa de analisá-lo, então se é um bem sucedido TryParse para formatá-lo com minha própria stringformatter personalizado para fazê-lo ter anterior zeros. Eu estou esperando por algo mais simples e performance.

Editar
Acabei fazendo um IComparer Joguei no meu Utils biblioteca para uso posterior.
Enquanto eu estava com ele eu joguei duplas na mistura também.

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

Talvez você poderia ir com uma abordagem mais genérica e usar um naturais classificação algoritmo como o C # implementação aqui .

Answer 2

Duas maneiras vêm à mente, não tenho certeza que é de maior performance. Implementar um 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() );

Ou, dividir a seqüência em números e não números, em seguida, classificar cada subgrupo, finalmente, juntar-se aos resultados classificados; 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

Use a outra sobrecarga de OrderBy que leva um parâmetro IComparer.

Você pode então implementar seu próprio IComparer que usos int.TryParse para dizer se é um número ou não.

Answer 4

Eu diria que você poderia dividir os valores utilizando uma RegularExpression (assumindo que tudo é um int) e, em seguida, voltar-las juntos.

//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+$", item)) {
        numbers.Add(int.Parse(item));
    }
    else {
        words.Add(item);
    }
}

Em seguida, com suas duas listas é possível classificar cada um deles e, em seguida, fundi-los de volta juntos em qualquer formato que você quiser.

Answer 5

Você poderia simplesmente usar a função fornecido pela API Win32:

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

e chamá-lo de um IComparer como outros têm mostrado.

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

Ele ainda faz a conversão, mas apenas uma vez / item.

Answer 7

Você pode usar um comparador personalizado - a declaração de pedidos, então, seria:

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

onde MyComparer é definido assim:

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

Embora isso possa parecer um pouco detalhado, que encapsula a lógica de ordenação em um tipo adequado. Você pode, então, se quiser, facilmente sujeitos a Comparer para testes automatizados (teste de unidade). Também é reutilizável.

(Pode ser possível fazer o algoritmo um pouco mais clara, mas este foi o melhor que eu poderia rapidamente jogar juntos.)

Answer 8

Você também pode "enganar" em algum sentido. Com base na sua descrição do problema, Você sabe qualquer cadeia de comprimento 2 será um número. Assim, apenas uma espécie todas as cordas de comprimento 1. E em seguida, classificar todas as strings de comprimento 2. E, em seguida, fazer um monte de troca para reordenar suas cordas na ordem correta. Essencialmente, o processo vai funcionar da seguinte forma: (. Assumindo os seus dados estão em uma matriz)

Passo 1: empurram todos cadeias de comprimento 2 para o final da matriz. Manter o controle de quantas você tem.

Passo 2:. Em lugar de ordenar as cordas de comprimento 1 e cadeias de comprimento 2

Passo 3:. Pesquisa binária para 'a' que seria no limite de suas duas metades

Passo 4:. Troque suas duas seqüências de dígitos com as letras como necessário

Dito isto, embora esta abordagem irá funcionar, não envolve expressões regulares, e não tenta analisar os valores não-int como um int - Eu não recomendo. Você vai estar escrevendo significativamente mais código do que outras abordagens já foi sugerido. Ele ofusca a ponto de que você está tentando fazer. Ele não funciona se você de repente ficar duas letras Cordas ou três dígitos Strings. Etc. Eu só estou incluindo-lo para mostrar como você pode olhar para os problemas de forma diferente, e chegar a soluções alternativas.

Answer 9

Use a Schwartziana Transform para executar O (n) conversões!

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

Eu tive um problema semelhante e desembarcou aqui:. Ordenação cordas que têm um sufixo numérico como no exemplo a seguir

Original:

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

resultado Classificação padrão:

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

desejado tipo resultar:

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

Acabei usando um costume Comparer:

public class NaturalComparer : IComparer
{

    public NaturalComparer()
    {
        _regex = new Regex("\\d+$", 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)