sort string-numbers

Question

Possible Duplicate:
Natural Sort Order in C#

I have a list with a lot of numbers in it. But they are saved as strings because of some additional letters.

My list looks something like this:

1
10
11
11a
11b
12
2
20
21a
21c
A1
A2
...

but it should look like this

1
2
10
11a
11b
...
A1
A2
...

How do i sort my list to get this result?

Solution 1

Going by the previous comments, I would also implement a custom IComparer<T> class. From what I can gather, the structure of the items is either a number, of a combination of a number followed by a letter(s). If this is the case, the following IComparer<T> implementation should work.

public class CustomComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        var regex = new Regex("^(d+)");

        // run the regex on both strings
        var xRegexResult = regex.Match(x);
        var yRegexResult = regex.Match(y);

        // check if they are both numbers
        if (xRegexResult.Success && yRegexResult.Success)
        {
            return int.Parse(xRegexResult.Groups[1].Value).CompareTo(int.Parse(yRegexResult.Groups[1].Value));
        }

        // otherwise return as string comparison
        return x.CompareTo(y);
    }
}

With this IComparer<T>, you'll be able to sort your list of string by doing

var myComparer = new CustomComparer();
myListOfStrings.Sort(myComparer);

This has been tested with the following items:

2, 1, 4d, 4e, 4c, 4a, 4b, A1, 20, B2, A2, a3, 5, 6, 4f, 1a

and gives the result:

1, 1a, 2, 20, 4a, 4b, 4c, 4d, 4e, 4f, 5, 6, A1, A2, a3, B2

Solution 2

Since this includes many string operations, regex etc., I don't think it is an efficient algorithm but It seems to work.

List<string> list1 = new List<string>() { "11c22", "1", "10", "11", "11a", "11b", "12", "2", "20", "21a", "21c", "A1", "A2" };
List<string> list2 = new List<string>() { "File (5).txt", "File (1).txt", "File (10).txt", "File (100).txt", "File (2).txt" };
var sortedList1 = NaturalSort(list1).ToArray();
var sortedList2 = NaturalSort(list2).ToArray();

---

public static IEnumerable<string> NaturalSort(IEnumerable<string> list)
{
    int maxLen = list.Select(s => s.Length).Max();
    Func<string, char> PaddingChar = s => char.IsDigit(s[0]) ? ' ' : char.MaxValue;

    return list
            .Select(s =>
                new
                {
                    OrgStr = s,
                    SortStr = Regex.Replace(s, @"(\d+)|(\D+)", m => m.Value.PadLeft(maxLen, PaddingChar(m.Value)))
                })
            .OrderBy(x => x.SortStr)
            .Select(x => x.OrgStr);
}

Solution 3

Well, you need to extract the number from each string and then sort the list of strings based on the list of numbers as keys. Do this in two steps.

To extract the number from each string, the simplest way I think is to use a regular expression - look for a match for (\d+) (if you have negative or decimal numbers, you'll have to use a different regular expression). Let's say you did that in a function called ExtractNumber

Now you can use some creative LINQ to sort, like this:

strings.Select(s=>new { key=ExtractNumber(s), value=s }) // Create a key-value pair
       .OrderBy(p=>p.key)                                // Sort by key
       .Select(p=>p.Value);                              // Extract the values