Sorting 50+-digit numbers in array

Question

I have array of strings containing 50+-digit numbers. I need to convert them to real-world integers and order them in asceding. It works when I have numbers with different size number of digits, but in this case where all numbers having same size number of digits it won't work:

string[] unsorted = {"324141241413213123123123132131451231231321363435243321413153412465745238454211425241244252423234234", "324141241413213123123123132131451231231321363435243321413153412465745238454211425241244252423234235"
        ,"324141241413213123123123132131451231231321363435243321413153412465745238454211425241244252423234200","324141241413213123123123132131451231231321363435243321413153412465745238454211425241244252423234100","324141241413213123123123132131451231231321363435243321413153412465745238454211425241244252423234731"};
var sorted = unsorted.OrderBy(s => double.Parse(s));

What's the best solution?

What kind of numbers, things that can be parsed to BigInteger? — harold, Feb 21 '17 at 21:55
If you have a data type issue (as far as capacity for your numbers), you can pad the strings with leading zeros and sort them alphabetically. — snow_FFFFFF, Feb 21 '17 at 22:02
@snow_FFFFFF: That would make the solution character-encoding (hence platform) dependent. Though I suppose that the alphabetic order of the characters [0-9] is preserved in all platforms... But still... That said, I'm not sure what the "C# standard" says about character-encoding. If it is an actual part of the standard, then I guess that my comment is irrelevant. — barak manos, Feb 21 '17 at 22:06
Too short, not enough details. Provide sample data and post expected vs actual results. — H H, Feb 21 '17 at 22:16
@harold I tried with BigInteger. Now it pass all test cases. Thank you :) — gagro, Feb 21 '17 at 22:31
@barakmanos: If you want to know what the spec says, it's published on the internet in several formats. The spec says that C# strings are UTF-16-encoded. — Eric Lippert, Feb 21 '17 at 22:35

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

3

If you are working with integers you can parse them to BigInteger (both double and decumal are too short for such numbers, e.g. Decimal.MaxValue == 79228162514264337593543950335 which is 29 digits only):

using System.Numerics;

...

string[] data = ...

var ordered = data
  .OrderBy(item => BigInteger.Parse(item))
  .ToArray(); // if you want materialization to array

If you're working with non-negative integers you can sort them by length and then lexicographically (no need in conversion):

string[] data = ...

var ordered = data
  .OrderBy(item => item.Length)
  .ThenBy(item => item)
  .ToArray(); // if you want materialization to array

The same approach for any integers (see Jason P Sallinger's comment) is also possible but not that elegant:

  var ordered = data
    .Where(item => item.StartsWith("-"))
    .OrderByDescending(item => item.Length)
    .ThenByDescending(item => item)
    .Concat(data
       .Where(item => !item.StartsWith("-"))
       .OrderBy(item => item.Length)
       .ThenBy(item => item))
    .ToArray();

Finally, please have a look at Natural Sort Order in C#

edited May 23 '17 at 10:29

Community

1
1

answered Feb 21 '17 at 22:04

Dmitry Bychenko

180,369
20
160
215

1

If you did have negative integers, you could split the set, do it in two passes, then merge the two arrays – Jason P Sallinger Feb 21 '17 at 22:08
@Jason P Sallinger: Thank you, I see! But the implementation of the idea will be combersome. – Dmitry Bychenko Feb 21 '17 at 22:17
true. At least it would be a step in the direction of fail-safe – Jason P Sallinger Feb 21 '17 at 22:18
1

@DmitryBychenko I tried with both solutions and both off them pass all test cases. Thank you :) – gagro Feb 21 '17 at 22:30
@gagro: you are welcome! – Dmitry Bychenko Feb 21 '17 at 22:32

score 0 · Answer 2 · answered Feb 21 '17 at 22:39

Assuming they're trimmed (no leading zeros) positive integers with no commas then:

unsorted.OrderBy(s => s.Length).ThenBy(s => s)

Would work because an untrimmed integer that is longer than another untrimmed number will be larger than it.

For negatives too:

unsorted.Order(s => s[0] != '-').ThenBy(s => s.Length).ThenBy(s => s)

Since booleans sort false before true and you want strings starting with - to come before those that don't.

If things are more complicated than that I'd use an IEqualityComparer<string> with a Compare method that:

If only one had - then it comes first.
Else if they both have - then trim off the -, call itself with the result and then negated that result.
Trim any thousands groupings (, in English-language use).
Get the length to the decimal separator (. in English-language use) in each or the full length if there is none. If different, shortest is smallest.
Ordinal string comparison.

Problem was I used double instead of BigInteger because double can't handle those big numbers. Changing double to BigInteger resolve the issue. — gagro, Feb 22 '17 at 13:09

user96564 · Answer 3 · 2017-02-21T23:38:31.653

-1

Try this; (A Simple solution in linq) it works for both positive and negative integers numbers.

string[] array = { "2525213", "2525211", "-2525214" };

        var result = array.OrderBy(x => BigInteger.Parse(x));

        foreach (var item in result)
        {
            Console.WriteLine(item);
        }
    }

edited Feb 21 '17 at 23:38

answered Feb 21 '17 at 22:35

user96564

1,578
5
24
42

Well, that's basically copied and pasted from @Dmitry answer, and those are not 50+-digit numbers. – gagro Feb 22 '17 at 13:05

Sorting 50+-digit numbers in array

3 Answers3