0
\$\begingroup\$

Consider an array of numeric strings where each string is a positive whole number. Sort the array's string elements in ascending order of their numeric values, and return the sorted array.

Return: string[n]: the array sorted in numeric order.

Constraints: Each string is guaranteed to represent a positive whole integer. There will be no leading zeros.

Sample Input:

6
31415926535897932384626433832795
1
3
10
3
5

Sample Output:

1
3
3
5
10
31415926535897932384626433832795

Code:

using System;
using System.IO;
using System.Linq;

namespace Big_Sorting
{
    class Solution
    {
        static string[] BigSorting(string[] unsorted) => unsorted.OrderBy(s => s.Length).ThenBy(s => s).ToArray();

        static void Main()
        {
            TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

            int n = Convert.ToInt32(Console.ReadLine());

            string[] unsorted = new string[n];

            for (int i = 0; i < n; i++)
            {
                unsorted[i] = Console.ReadLine();
            }

            textWriter.WriteLine(string.Join("\n", BigSorting(unsorted)));

            textWriter.Flush();
            textWriter.Close();
        }
    }
}

I need to improve upon this code. Priority for me is performance here. If the array is becomes long in length this begins to slow down. This is functional and working. I just want to get it as fast as possible.

The code works fine for test cases like this.

But has trouble with test case like this

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Can you clarify what you mean by "has trouble"? Is it just slow or does it produce the wrong results? \$\endgroup\$
    – Rick Davin
    Jan 29, 2021 at 13:11
  • 5
    \$\begingroup\$ Is that this? If so, why keep that secret? \$\endgroup\$ Jan 29, 2021 at 13:39
  • 1
    \$\begingroup\$ your test case links are no longer available. \$\endgroup\$
    – Malachi
    Jan 29, 2021 at 15:51
  • \$\begingroup\$ Link to test cases. gist.github.com/milliorn/aa632cc4a2d659e050bbdb8794a308c1 \$\endgroup\$
    – Milliorn
    Jan 29, 2021 at 17:37
  • \$\begingroup\$ Could you please include some measurement data? All optimization should start by understanding the current solution (what is the baseline, where is the bottleneck, how far is it from the expected behaviour, should it be fast for all sort of inputs, etc..) \$\endgroup\$ Feb 1, 2021 at 13:07

1 Answer 1

2
\$\begingroup\$

You have been posting in CodeReview for about 1 year, so while you are still learning C# and a hobbyist, you are not a total newbie. Therefore, you should expect the reviews to be a little more critical. Do understand that "critical" does not mean "mean spirited" but rather more blunt while also being constructive.

What disappoints me most in your code is its structure. You put almost everything in Main. I would challenge you to step back and look at the big picture of what goes on:

  1. UI Input - Ask for input values
  2. Business Logic - manipulate or process those input values
  3. UI Output

So you could make your Main to look similar to those items. This is a major principle to keep in mind: Separation of Concerns, namely your business logic and UI should be separate. But Separation of Concerns also applies to breaking up a monster method that is doing too much into smaller methods where each call does a specific thing.

There is also the .NET guideline that you should limit the scope of a variable. I am an old-timer who worked with VB and way back then it was common to define ALL the variables at the top of a method and then use them later. With .NET, this is not needed. In particular, I am referring to the variable textWriter. You define at the very top but start to use it at the bottom.

I also do not like the name textWriter. I personally would use a generic name of writer just in case you every change to a different implementation. But that really doesn't matter because you don't need that variable at all. You use 4 lines of code when only 1 is needed:

File.WriteAllLines(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), 
                   BigSorting(unsorted));

I have also observed in a history of your posts, and the same is true here, that you code to a specific implementation of array. Your methods can have a broader reach and re-usability if you coded to a more basic implementation, such as IList or even IEnumerable. Consider:

static IOrderedEnumerable<string> BigSorting(IEnumerable<string> items) => items.OrderBy(s => s.Length).ThenBy(s => s);

The input is no longer restricted to being an array, and I do not create an entirely new array for output. I also changed the parameter name to items because I don't care if someone inputs a unsorted collection or one sorted in some other order. Doesn't matter to the method.

What if you wanted to output to an array? Then use .ToArray() when you make the call BigSorting rather than doing it inside BigSorting.

So that addresses quick and simple sorting use LINQ, which produces a 2nd array. There is an alternative that doesn't require a 2nd array. I haven't tested with huge number of elements or crazy long values. I leave that to you and hopefully you will find it more performant.

I am referring to making a custom IComparer. See this link. Example:

public class NumericStringComparer : IComparer<string>
{
    // https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?view=net-5.0#System_Array_Sort__1___0___System_Collections_Generic_IComparer___0__
    public int Compare(string x, string y)
    {
        // Compare x and y as numbers without leading zeroes.
        if (x == null)
        {
            return (y == null) ? 0 : -1;
        }
        if (y == null)
        {
            return 1;
        }
        if (x.Length < y.Length)
        {
            return -1;
        }
        if (y.Length < x.Length)
        {
            return 1;
        }
        return x.CompareTo(y);
    }
}

Now you would use it like:

Array.Sort(unsorted, new NumericStringComparer());
File.WriteAllLines(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), 
                       unsorted);

Except I now have a problem with the name "unsorted". While the array containing inputs was initially unsorted, I later sorted in-place to that very same array, so in WriteAllLines the name choice of unsorted is misleading. Thus, I would choose a generic name of items for the array.

\$\endgroup\$
7
  • \$\begingroup\$ @Rick thanks for spending the time again on something I post. Much appreciated. To answer some of your post I will likely only post code that has 100% of my work in it. I can't explain what someone else did. Get some context you can read the other two post I made on this page. Regardless I do in other places still have issues with Separation of Concerns. I"m sorry you did a write up on that part but it did give me some insight on some things. I keep forgetting about IEnumerable despite using it more often lately. I tried your suggestion with IComparer an it failed the same as my solution. \$\endgroup\$
    – Milliorn
    Jan 29, 2021 at 17:30
  • \$\begingroup\$ @Rick however I really do like what you did with IComparer an although its more code I like the approach an ability to really hone in on what I want it to do. Great advice. \$\endgroup\$
    – Milliorn
    Jan 29, 2021 at 17:31
  • \$\begingroup\$ @Milliorn On using IComparer you need to ask yourself what is more important to you: do you want the code to be performant or do you want the code to be short? Oftentimes, you can't have both. \$\endgroup\$
    – Rick Davin
    Jan 29, 2021 at 17:57
  • \$\begingroup\$ @Milliorn an it failed what does it mean? \$\endgroup\$
    – aepot
    Feb 1, 2021 at 1:01
  • \$\begingroup\$ @aepot there is a test that checks a very long list of elements and almost all those elements length are the same. \$\endgroup\$
    – Milliorn
    Feb 1, 2021 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.