Sorting List<String> in C#

Question

How to sort a List based on the item's integer value

The list is like

"1"
"5"
"3"
"6"
"11"
"9"
"NUM1"
"NUM0"

The result should be like

"1"
"3"
"5"
"6"
"9"
"11"
"NUM0"
"NUM1"

is there any idea to do this using LINQ or Lambda expression?

Thanks in advance

Answer 1

How about:

    list.Sort((x, y) =>
    {
        int ix, iy;
        return int.TryParse(x, out ix) && int.TryParse(y, out iy)
              ? ix.CompareTo(iy) : string.Compare(x, y);
    });

Answer 2

This is called a "natural sort order", and is usually employed to sort items like those you have, like filenames and such.

Here's a naive (in the sense that there are probably plenty of unicode-problems with it) implementation that seems to do the trick:

You can copy the code below into LINQPad to execute it and test it.

Basically the comparison algorithm will identify numbers inside the strings, and handle those by padding the shortest one with leading zeroes, so for instance the two strings "Test123Abc" and "Test7X" should be compared as though they were "Test123Abc" and "Test007X", which should produce what you want.

However, when I said "naive", I mean that I probably have tons of real unicode problems in here, like handling diacritics and multi-codepoint characters. If anyone can give a better implementation I would love to see it.

Notes:

• The implementation does not actually parse the numbers, so arbitrarily long numbers should work just fine
• Since it doesn't actually parse the numbers as "numbers", floating point numbers will not be handled properly, "123.45" vs. "123.789" will be compared as "123.045" vs. "123.789", which is wrong.

Code:

void Main()
{
    List<string> input = new List<string>
    {
        "1", "5", "3", "6", "11", "9", "A1", "A0"
    };
    var output = input.NaturalSort();
    output.Dump();
}

public static class Extensions
{
    public static IEnumerable<string> NaturalSort(
        this IEnumerable<string> collection)
    {
        return NaturalSort(collection, CultureInfo.CurrentCulture);
    }

    public static IEnumerable<string> NaturalSort(
        this IEnumerable<string> collection, CultureInfo cultureInfo)
    {
        return collection.OrderBy(s => s, new NaturalComparer(cultureInfo));
    }

    private class NaturalComparer : IComparer<string>
    {
        private readonly CultureInfo _CultureInfo;

        public NaturalComparer(CultureInfo cultureInfo)
        {
            _CultureInfo = cultureInfo;
        }

        public int Compare(string x, string y)
        {
            // simple cases
            if (x == y) // also handles null
                return 0;
            if (x == null)
                return -1;
            if (y == null)
                return +1;

            int ix = 0;
            int iy = 0;
            while (ix < x.Length && iy < y.Length)
            {
                if (Char.IsDigit(x[ix]) && Char.IsDigit(y[iy]))
                {
                    // We found numbers, so grab both numbers
                    int ix1 = ix++;
                    int iy1 = iy++;
                    while (ix < x.Length && Char.IsDigit(x[ix]))
                        ix++;
                    while (iy < y.Length && Char.IsDigit(y[iy]))
                        iy++;
                    string numberFromX = x.Substring(ix1, ix - ix1);
                    string numberFromY = y.Substring(iy1, iy - iy1);

                    // Pad them with 0's to have the same length
                    int maxLength = Math.Max(
                        numberFromX.Length,
                        numberFromY.Length);
                    numberFromX = numberFromX.PadLeft(maxLength, '0');
                    numberFromY = numberFromY.PadLeft(maxLength, '0');

                    int comparison = _CultureInfo
                        .CompareInfo.Compare(numberFromX, numberFromY);
                    if (comparison != 0)
                        return comparison;
                }
                else
                {
                    int comparison = _CultureInfo
                        .CompareInfo.Compare(x, ix, 1, y, iy, 1);
                    if (comparison != 0)
                        return comparison;
                    ix++;
                    iy++;
                }
            }

            // we should not be here with no parts left, they're equal
            Debug.Assert(ix < x.Length || iy < y.Length);

            // we still got parts of x left, y comes first
            if (ix < x.Length)
                return +1;

            // we still got parts of y left, x comes first
            return -1;
        }
    }
}

Answer 3

Try writing a small helper class to parse and represent your tokens. For example, without too many checks:

public class NameAndNumber
{
    public NameAndNumber(string s)
    {
        OriginalString = s;
        Match match = Regex.Match(s,@"^(.*?)(\d*)$");
        Name = match.Groups[1].Value;
        int number;
        int.TryParse(match.Groups[2].Value, out number);
        Number = number; //will get default value when blank
    }

    public string OriginalString { get; private set; }
    public string Name { get; private set; }
    public int Number { get; private set; }
}

Now it becomes easy to write a comparer, or sort it manually:

var list = new List<string> { "ABC", "1", "5", "NUM44", "3", 
                              "6", "11", "9", "NUM1", "NUM0" };

var sorted = list.Select(str => new NameAndNumber(str))
    .OrderBy(n => n.Name)
    .ThenBy(n => n.Number);

Gives the result:

1, 3, 5, 6, 9, 11, ABC, NUM0, NUM1, NUM44