Home > Back-end >  How to sort a List<String> of arbitrary large numbers?
How to sort a List<String> of arbitrary large numbers?

Time:08-14

In C#, how can you sort a list of large numbers in such a way that the negative numbers with a - minus-character are also in the right order?

I know an int can hold numbers with max. 10 digits and ulong can hold about 20 digit numbers. But I have a list of numbers with 24~30 digits, including negative numbers.

I figured the way to do this is add a string that is padded with 0's and then sort on that new string. So 1234 becomes 0001234. And for negative numbers -567 is becomes 9999432 because then it is sorted inversely. See code below

private void TestingList()
{
    // test values
    List<string> Values123 = new List<string> {
        "123456789012345678901234",
        "-61309282998165063700291",
        "72413799900717492396359",
        "-10076416403816370211636",
        "123191989931658420157210",
        "-675299502697548089298418",
        "554706403711546488433874",
        "-882666356021157245451325",
        "877873677336436172875781",
        "-695217734376922329970499"
    };
    //List<string> Values123 = new List<string> {"2222", "4444", "3333", "1111", "5555"};

    // create a sortable list, of type List<String, String>
    var Test123 = new List<KeyValuePair<string, string>>();
    foreach (var v in Values123)
    {
        Test123.Add(new KeyValuePair<string, string>(sortableValue(v), v));
    }

    // sort the list oin the sortable key
    var Sorted123 = Test123.OrderBy(x => x.Key).ToList();

    // print list
    foreach (var s in Sorted123)
    {
        Console.WriteLine(String.Format("{0} -> {1}", s.Key, s.Value));
    }

}

The function that creates the sortable string looks like this.

private string sortableValue(string val)
{
    if (val.IndexOf('-') < 0)
        // not negative
        return val.PadLeft(30, '0');
    else
    {
        // negative numbers
        var ret = "";
        foreach (char c in val) {
            var test123 = c;
            if ((c >= '0') && (c <= '9')) {
                // '0'..'9' = ascii 48..57
                //c = Convert.ToChar(48 57 - c);
                test123 = (char)(48   57 - c);
            } else if (c == '-') {
                test123 = '9';
            }
            ret  = test123;
        }
        return ret.PadLeft(30, '9');
    };
}

And the result is close to what I want, but not quite.

Key sorted                        String value
000000072413799900717492396359 ->   72413799900717492396359
000000123191989931658420157210 ->  123191989931658420157210
000000123456789012345678901234 ->  123456789012345678901234
000000554706403711546488433874 ->  554706403711546488433874
000000877873677336436172875781 ->  877873677336436172875781
999999117333643978842754548674 -> -882666356021157245451325
999999304782265623077670029500 -> -695217734376922329970499
999999324700497302451910701581 -> -675299502697548089298418
999999938690717001834936299708 ->  -61309282998165063700291
999999989923583596183629788363 ->  -10076416403816370211636

The sorted string values should be in this order:

-882666356021157245451325
-695217734376922329970499
-675299502697548089298418
 -61309282998165063700291
 -10076416403816370211636
  72413799900717492396359
 123191989931658420157210
 123456789012345678901234
 554706403711546488433874
 877873677336436172875781

Is there a way to get this result, by some extra sort option or something lke that? Or is there maybe a better way to go about this?

EDIT: I just realised I could also add one extra 0 or 9 to the sortedkeys to flip the positive and negative values and get the desired sorting. So change the two return lines like this (still a bit hackey but it gets the job done):

if (val.IndexOf('-') < 0)
    return "9"   val.PadLeft(30, '0'); // positive numbers
//etc.
    return "0"   ret.PadLeft(30, '9'); // negative numbers

CodePudding user response:

As mentioned in the comment System.Numeric.BigInteger is the way to go. All you have to do is:

IEnumerable<string> sorted123 = Values123.OrderBy(v => BigInteger.Parse(v));

And you get the result:

-882666356021157245451325
-695217734376922329970499
-675299502697548089298418
-61309282998165063700291
-10076416403816370211636
72413799900717492396359
123191989931658420157210
123456789012345678901234
554706403711546488433874
877873677336436172875781

Full example with .NET Fiddle here.

  • Related