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:

Use the Split function to get the individual numbers
Put the values into an object
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?

Can you be clearer on what you want? what's the difference between the sort you're getting and the sort you want? — David, Dec 08 '10 at 16:44
He wants them ordered in ascending order as per the example given, so 10 follows 9 rather than following 1. — rrrr-o, Dec 08 '10 at 16:50
I think Tarzan has a list of data in character order and wants it sorted by numeric order. — Paul Sasik, Dec 08 '10 at 16:50
Seeing how he hasn't bothered to chime in on the plethora of responses, I won't bother asking what his problem is with splitting the string. It's not "extra work," and runs in O(N) time. — 3Dave, Dec 09 '10 at 00:15

score 8 · Accepted Answer · edited May 23 '17 at 10:29

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

lets say we have following numbers `10 10.01 2 3 1.1 1.2 1` and I am getting wrong output : `1.1 1.2 1 2 3 10 10.01` can you help me with that?! — Kyabroudi, Sep 11 '16 at 11:44
This work almost perfectly. But non-decimal numbers will appear after decimal numbers. ex: 4.01, 4.10, 4 — Wildhorn, Sep 18 '20 at 18:54

score 3 · Answer 2 · answered Dec 08 '10 at 16:46

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).

My solution does quite what you explain. – VVS Dec 08 '10 at 22:26 — VVS, Dec 08 '10 at 22:26

Unmesh Kondolikar · Answer 3 · 2010-12-08T16:55:08.280

2

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.

edited Dec 08 '10 at 16:55

answered Dec 08 '10 at 16:49

Unmesh Kondolikar

9,256
4
38
51

No lambda? Little disappointing. Still, this is the most worthwhile solution. +1 – Brad Christie Dec 08 '10 at 16:52
The OP wants to avoid string splitting. – VVS Dec 08 '10 at 17:19
That has to be done one way or the other. He can also use numString.Where(char.IsDigit) to remove '.' (dot) from the string and then compare the strings char by char. – Unmesh Kondolikar Dec 08 '10 at 17:28
Well .. the point is that the string has to be parsed before you can carry out your comparison. Some use Split and some Substring and IndexOf. But the parsing has to be done anyway. – Unmesh Kondolikar Dec 09 '10 at 04:30

Daniel Brückner · Answer 4 · 2010-12-08T17:14:01.273

2

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.

edited Dec 08 '10 at 17:14

answered Dec 08 '10 at 17:07

Daniel Brückner

59,031
16
99
143

score 1 · Answer 5 · answered Aug 16 '12 at 22:38

You can use the awesome AlphanumComparator Alphanum natural sort algorithm by David Koelle.

Code:

OrderBy(o => o.MyString, new AlphanumComparator())

If you're gonna use the C# version change it to:

AlphanumComparator : IComparer<string>

and

public int Compare(string x, string y)

score 1 · Answer 6 · answered Dec 08 '10 at 16:52

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.

score 1 · Answer 7 · answered Dec 08 '10 at 17:00

Not really, though you may be able to use Regexes or Linq to avoid too much wheel-reinventing. Keep in mind it will cost you much the same computationally to use something built-in as to roll your own.

Try this:

List<string> myList = GetNumberStrings();

myList.Select(s=>s.Split('.')).ToArray().
   .Sort((a,b)=>RecursiveCompare(a,b))
   .Select(a=>a.Aggregate(new StringBuilder(),
      (s,sb)=>sb.Append(s).Append(".")).Remove(sb.Length-1, 1).ToString())
   .ToList();

...

public int RecursiveCompare(string[] a, string[] b)
{
    return RecursiveCompare(a,b,0)
}

public int RecursiveCompare(string[] a, string[] b, int index)
{
    return index == a.Length || index == b.Length 
        ? 0 
        : a[index] < b[index] 
            ? -1 
            : a[index] > b[index] 
                ? 1 
                : RecursiveCompare(a,b, index++);
}

Not the most compact, but it should work and you could use a y-combinator to make the comparison a lambda.

Looks quite expensive and I find it hard to understand that what you're doing in that big select statement is just sorting. — VVS, Dec 08 '10 at 22:30

3Dave · Answer 8 · 2010-12-08T17:52:54.760

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

Ah. =) The OP needs to reevaluate his priorities. The string split is about the least expensive operation involved. — 3Dave, Dec 09 '10 at 00:13

score 0 · Answer 9 · answered Dec 08 '10 at 16:52

0

In addition to implementing your own IComparer as Jon mentions, if you call ToList() on your array, you can call the .Sort() method and pass in a function parameter that compares two values, as shown here: http://msdn.microsoft.com/en-us/library/w56d4y5z.aspx

answered Dec 08 '10 at 16:52

Keith

5,311
3
34
50

I mentioned it as an alternative. – Keith Dec 08 '10 at 22:36

How can I use C# to sort values numerically?

9 Answers9

Linked