How can I use C# to sort values numerically?

Question

I have a string that contains numbers separated by periods. When I sort it appears like this since it is a string: (ascii char order)

3.9.5.2.1.1
3.9.5.2.1.10
3.9.5.2.1.11
3.9.5.2.1.12
3.9.5.2.1.2
3.9.5.2.1.3
3.9.5.2.1.4

etc.

I want it to sort like this: (in numeric order)

3.9.5.2.1.1
3.9.5.2.1.2
3.9.5.2.1.3
...
3.9.5.2.1.9
3.9.5.2.1.10
3.9.5.2.1.11
3.9.5.2.1.12

I know that I can:

1. Use the Split function to get the individual numbers
2. Put the values into an object
3. Sort the object

I prefer to avoid all of that work if it is duplicating existing functionality. Is a method in the .net framework that does this already?

Answer 1

What you are looking for is the natural sort order and Jeff Atwood bloged about it and has links to implementations in different languages. The .NET Framework does not contain an implementation.

Answer 2

Split each string by '.', iterate through the components and compare them numerically.

This code also assumes that the number of components is signficant (a string '1.1.1' will be greater than '2.1'. This can be adjusted by altering the first if statement in the Compare method below.

    int Compare(string a, string b)
    {
        string[] aParts = a.Split('.');
        string[] bParts = b.Split('.');

        /// if A has more components than B, it must be larger.
        if (aParts.Length != bParts.Length)
            return (aParts.Length > bParts.Length) ? 1 : -1;

        int result = 0;
        /// iterate through each numerical component

        for (int i = 0; i < aParts.Length; i++)
            if ( (result = int.Parse(aParts[i]).CompareTo(int.Parse(bParts[i]))) !=0 )
                return result;

        /// all components are equal.
        return 0;
    }



    public string[] sort()
    {
        /// initialize test data
        string l = "3.9.5.2.1.1\n"
        + "3.9.5.2.1.10\n"
        + "3.9.5.2.1.11\n"
        + "3.9.5.2.1.12\n"
        + "3.9.5.2.1.2\n"
        + "3.9.5.2.1.3\n"
        + "3.9.5.2.1.4\n";

        /// split the large string into lines
        string[] arr = l.Split(new char[] { '\n' },StringSplitOptions.RemoveEmptyEntries);
        /// create a list from the array
        List<string> strings = new List<string>(arr);
        /// sort using our custom sort routine
        strings.Sort(Compare);
        /// concatenate the list back to an array.
        return strings.ToArray();
    }

Answer 3

Here's my working solution that also takes care of strings that are not in the right format (e.g. contain text).

The idea is to get the first number within both strings and compare these numbers. If they match, continue with the next number. If they don't, we have a winner. If one if these numbers isn't a number at all, do a string comparison of the part, which wasn't already compared.

It would be easy to make the comparer fully compatible to natural sort order by changing the way to determine the next number.

Look at that.. just found this question.

The Comparer:

class StringNumberComparer : IComparer<string>
{
    public int Compare(string x, string y)
    {
        int compareResult;
        int xIndex = 0, yIndex = 0;
        int xIndexLast = 0, yIndexLast = 0;
        int xNumber, yNumber;
        int xLength = x.Length;
        int yLength = y.Length;

        do
        {
            bool xHasNextNumber = TryGetNextNumber(x, ref xIndex, out xNumber);
            bool yHasNextNumber = TryGetNextNumber(y, ref yIndex, out yNumber);

            if (!(xHasNextNumber && yHasNextNumber))
            {
                // At least one the strings has either no more number or contains non-numeric chars
                // In this case do a string comparison of that last part
                return x.Substring(xIndexLast).CompareTo(y.Substring(yIndexLast));
            }

            xIndexLast = xIndex;
            yIndexLast = yIndex;

            compareResult = xNumber.CompareTo(yNumber);
        }
        while (compareResult == 0
            && xIndex < xLength
            && yIndex < yLength);

        return compareResult;
    }

    private bool TryGetNextNumber(string text, ref int startIndex, out int number)
    {
        number = 0;

        int pos = text.IndexOf('.', startIndex);
        if (pos < 0) pos = text.Length;

        if (!int.TryParse(text.Substring(startIndex, pos - startIndex), out number))
            return false;

        startIndex = pos + 1;

        return true;
    }
}

Usage:

public static void Main()
{
    var comparer = new StringNumberComparer();

    List<string> testStrings = new List<string>{
        "3.9.5.2.1.1",
        "3.9.5.2.1.10",
        "3.9.5.2.1.11",
        "3.9.test2",
        "3.9.test",
        "3.9.5.2.1.12",
        "3.9.5.2.1.2",
        "blabla",
        "....",
        "3.9.5.2.1.3",
        "3.9.5.2.1.4"};

    testStrings.Sort(comparer);

    DumpArray(testStrings);

    Console.Read();
}

private static void DumpArray(List<string> values)
{
    foreach (string value in values)
    {
        Console.WriteLine(value);
    }
}

Output:

....
3.9.5.2.1.1
3.9.5.2.1.2
3.9.5.2.1.3
3.9.5.2.1.4
3.9.5.2.1.10
3.9.5.2.1.11
3.9.5.2.1.12
3.9.test
3.9.test2
blabla

Answer 4

No, I don't believe there's anything in the framework which does this automatically. You could write your own IComparer<string> implementation which doesn't do any splitting, but instead iterates over both strings, only comparing as much as is required (i.e. parsing just the first number of each, then continuing if necessary etc) but it would be quite fiddly I suspect. It would also need to make assumptions about how "1.2.3.4.5" compared with "1.3" for example (i.e. where the values contain different numbers of numbers).

Answer 5

Is it possible for you to pad your fields to the same length on the front with 0? If so, then you can just use straight lexicographic sorting on the strings. Otherwise, there is no such method built in to the framework that does this automatically. You'll have to implement your own IComparer<string> if padding is not an option.

Answer 6

Since the comparison you want to do on the strings is different from how strings are normally compared in .Net, you will have to use a custom string string comparer

 class MyStringComparer : IComparer<string>
        {
            public int Compare(string x, string y)
            {
                // your comparison logic
                // split the string using '.' separator
                // parse each string item in split array into an int
                // compare parsed integers from left to right
            }
        }

Then you can use the comparer in methods like OrderBy and Sort

var sorted = lst.OrderBy(s => s, new MyStringComparer());

lst.Sort(new MyStringComparer());

This will give you the desired result. If not then just tweak the comparer.