Ordinamento di numeri misti e stringhe

Question

Ho una lista di stringhe che possono contenere una lettera o una rappresentazione di stringa di un int (max 2 cifre). Devono essere ordinati alfabeticamente o (quando è effettivamente 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 coinvolgono formattarlo con il tentativo di analizzarlo, poi, se si tratta di un TryParse successo per formattare con il mio possedere il proprio stringformatter personalizzato per renderlo preceduto da zeri. Sto sperando in qualcosa di più semplice e performante.

Modifica
ho finito per fare un IComparer Buttai nella mia libreria Utils per un uso successivo.
Mentre ero lì ho buttato anche il doppio 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 si potrebbe optare per un approccio più generico e utilizzare un algoritmo natural sorting come l'implementazione C# here.

Answer 2

direi che si potrebbe dividere i valori utilizzando un'espressione regolare (supponendo che tutto è un int) e poi ricongiungersi 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+$", item)) { 
     numbers.Add(int.Parse(item)); 
    } 
    else { 
     words.Add(item); 
    } 
} 

poi con le due liste è possibile ordinare ciascuno di essi e quindi unire di nuovo insieme in qualsiasi formato che si desidera.

Answer 3

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

È quindi possibile implementare il proprio IComparer che utilizza int.TryParse per indicare se si tratta di un numero o meno.

Answer 4

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

lo fa ancora la conversione, ma solo una volta/item.

Answer 5

Due modi vengono in mente, non sono sicuro che sia più performante. Implementare 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 i numeri, poi ordinare ogni sottogruppo, infine unire i risultati ordinati; qualcosa di simile:

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 6

Si potrebbe utilizzare un operatore di confronto personalizzato - la dichiarazione ordinamento sarebbe allora:

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

dove MyComparer è definita 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); 
    } 
} 

Anche se questo può sembrare un bit verbose, incapsula la logica di ordinamento in un tipo corretto. È quindi possibile, se lo si desidera, sottoporre facilmente il comparatore a test automatici (test dell'unità). È anche riutilizzabile.

(Potrebbe essere possibile per rendere l'algoritmo di un po 'più chiaro, ma questo era il meglio che potessi gettare rapidamente insieme.)

Answer 7

Si potrebbe anche "barare" in un certo senso.In base alla tua descrizione del problema, sai che ogni stringa di lunghezza 2 sarà un numero. Quindi ordina solo tutte le stringhe di lunghezza 1. E poi ordina tutte le stringhe di lunghezza 2. E poi fai un po 'di scambio per riordinare le tue stringhe nell'ordine corretto. In sostanza, il processo funzionerà come segue: (presupponendo che i dati siano in un array.)

Passaggio 1: Spingere tutte le stringhe di lunghezza 2 alla fine dell'array. Tenendo traccia di quanti ne hai.

Fase 2: Al posto sorta l'stringhe di lunghezza 1 e le stringhe di lunghezza 2.

Fase 3: La ricerca binaria per 'a' che sarebbe sul confine dei vostri due metà.

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

Detto questo, mentre questo approccio funziona, non coinvolge le espressioni regolari e non tenta di analizzare i valori non int come int - non lo consiglio. Scriverete molto più codice rispetto ad altri approcci già suggeriti. Oscura il punto di ciò che stai cercando di fare. Non funziona se ottieni improvvisamente stringhe di due lettere o stringhe di tre cifre. Ecc. Sto solo includendolo per mostrare come puoi guardare i problemi in modo diverso e trovare soluzioni alternative.

Answer 8

Si potrebbe utilizzare la funzione provided by the Win32 API:

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

e chiamare da un IComparer come altri hanno mostrato.

Answer 9

Utilizzare un 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 sbarcarono qui: l'ordinamento delle stringhe che hanno un suffisso numerico come nel seguente esempio.

originale: Ordina risultati

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

predefinito:

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

desiderata Ordina risultati:

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

ho finito per usare un operatore di confronto personalizzato:

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)