Ordinamento di numeri e stringhe misti

Question

Ho un elenco di stringhe che possono contenere una lettera o una rappresentazione di stringa di un int (max 2 cifre). Devono essere ordinati in ordine alfabetico o (quando in realtà è un int) sul valore numerico che rappresenta.

Esempio:

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

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

Quello che vorrei è

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

Ho qualche idea che coinvolga la formattazione con il tentativo di analizzarlo, quindi se è un tryparse di successo formattarlo con il mio stringformatter personalizzato per renderlo con zeri precedenti. Spero in qualcosa di più semplice e performante.

Modifica
Ho finito per creare un IComparer che ho scaricato nella mia libreria Utils per un uso successivo.
Mentre ero lì ho anche lanciato doppi nel mix.

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

Forse potresti scegliere un approccio più generico e utilizzare un natural algoritmo di ordinamento come l'implementazione di C # qui .

Answer 2

Mi vengono in mente due modi, non sono sicuro di quale sia il più performante. Implementa un IComparer personalizzato:

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

Oppure, dividere la sequenza in numeri e non numeri, quindi ordinare ogni sottogruppo, infine unire i risultati ordinati; qualcosa come:

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

Usa l'altro sovraccarico di OrderBy che accetta un parametro IComparer .

Puoi quindi implementare il tuo IComparer che usa int. TryParse per dire se è un numero o meno.

Answer 4

Direi che potresti dividere i valori usando RegularExpression (supponendo che tutto sia un int) e quindi ricongiungerli insieme.

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

Quindi con i tuoi due elenchi puoi ordinare ciascuno di essi e poi riunirli nuovamente nel formato che desideri.

Answer 5

Potresti semplicemente utilizzare la funzione fornita dall'API Win32 :

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

e chiamalo da un IComparer come altri hanno mostrato.

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

Fa ancora la conversione, ma solo una volta / oggetto.

Answer 7

È possibile utilizzare un comparatore personalizzato: l'istruzione di ordinamento sarebbe quindi:

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

dove MyComparer è definito in questo modo:

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

Sebbene possa sembrare un po 'prolisso, incapsula la logica di ordinamento in un tipo appropriato. È quindi possibile, se lo si desidera, sottoporre facilmente il Comparatore a test automatici (test unitari). È anche riutilizzabile.

(Potrebbe essere possibile rendere l'algoritmo un po 'più chiaro, ma questo è stato il migliore che ho potuto rapidamente mettere insieme.)

Answer 8

Puoi anche " imbrogliare " in un certo senso. Sulla base della descrizione del problema, sai che qualsiasi stringa di lunghezza 2 sarà un numero. Quindi basta ordinare tutte le stringhe di lunghezza 1. E quindi ordinare tutte le stringhe di lunghezza 2. E poi fare un mucchio di scambi per riordinare le stringhe nell'ordine corretto. In sostanza il processo funzionerà come segue: (supponendo che i tuoi dati siano in un array.)

Passaggio 1: spingere tutte le stringhe di lunghezza 2 fino alla fine dell'array. Tenere traccia di quanti ne hai.

Passaggio 2: sul posto, ordina le stringhe di lunghezza 1 e le stringhe di lunghezza 2.

Passaggio 3: ricerca binaria di "a" che si troverebbe al limite delle due metà.

Passaggio 4: scambia le stringhe a due cifre con le lettere, se necessario.

Detto questo, mentre questo approccio funzionerà, non implica espressioni regolari e non tenta di analizzare i valori non int come int - non lo consiglio. Scriverai molto più codice di altri approcci già suggeriti. Offusca il punto di ciò che stai cercando di fare. Non funziona se ricevi improvvisamente stringhe di due lettere o stringhe di tre cifre. Ecc. Lo sto solo includendo per mostrare come è possibile esaminare i problemi in modo diverso e trovare soluzioni alternative.

Answer 9

Usa una Schwartzian Transform per eseguire conversioni 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

Ho avuto un problema simile e sono arrivato qui: l'ordinamento di stringhe che hanno un suffisso numerico come nell'esempio seguente.

Originale:

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

Risultato ordinamento predefinito:

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

Risultato dell'ordinamento desiderato:

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

Ho finito per usare un comparatore personalizzato:

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)