Sorting List<List<string>>

Question

I have a List of List which can be of variable but repeated width. For example:

var test = new List<List<string>>();
test.Add(new List<string> {"1","2","3"});
test.Add(new List<string> {"1","4","12"});
test.Add(new List<string> {"1","2","9"});
test.Add(new List<string> {"1","4","5"});
test.Add(new List<string> {"6","7","8"});

But it could also be:

var test = new List<List<string>>();
test.Add(new List<string> {"1","2","3","3","3"});
test.Add(new List<string> {"1","4","12","1","7"});
test.Add(new List<string> {"1","2","9","9","4"});
test.Add(new List<string> {"1","4","5","8","5"});
test.Add(new List<string> {"6","7","8","2","7"});

It will never be:

var test = new List<List<string>>();
test.Add(new List<string> {"1"});
test.Add(new List<string> {"1","5"});
test.Add(new List<string> {"1","2","3"});
test.Add(new List<string> {"1","5"});
test.Add(new List<string> {"6","7","8"});

And I would like to have the list ordered left column to right column like:

["1","2","3"];
["1","2","9"];
["1","4","5"];
["1","4","12"];
["6","7","8"];

The following is a little test I setup to see what I could come up with (https://dotnetfiddle.net/B5ljig):

var test = new List<List<string>>();
test.Add(new List<string> {"1","2","3"});
test.Add(new List<string> {"1","4","5"});
test.Add(new List<string> {"1","2","3"});
test.Add(new List<string> {"1","4","5"});
test.Add(new List<string> {"6","7","8"});

var query = test.AsQueryable();
query = query.OrderBy(a=>a[0]);
var max = categories.Select(a=>a.Count()).Max();
for (int i = 1; i < max; i++)
{
    query = query.ThenBy(a=>a[i]); // Error Here
}
var sorted = query.ToList();

Unfortunately the commented line errors with

'IQueryable>' does not contain a definition for 'ThenBy' and no accessible extension method 'ThenBy' accepting a first argument of type 'IQueryable>' could be found (are you missing a using directive or an assembly reference?)

Any ideas? Thoughts? Better ways.

Answer 1

The problem is

1) the overuse of IQueryable, you don't need it,

2) the fact that i is actually captured, and when the query is executed, you have all "then by" that use the same i == 3, the last value after the end of the for loop! (Hence, an out of bounds exception at runtime)

Here is a working version (dotnetFiddle):

    var query = test.OrderBy(a=>a[0]);
    //var max = test.Select(a=>a.Count()).Max(); // If you say all lists have the same length, use `First(a => a.Count())` instead! And if they don't, then this will lead to an exception.

    for (int i = 1; i < max; i++)
    {
        var j = i; // Intermediary variable so that 'global' i is not captured.
        query = query.ThenBy(a=>a[j]);
    };
    var sorted = query.ToList();

On additional note, there are other solutions that use different approaches, already given, I think they feel more "idiomatic" for C# with the IComparer

Answer 2

If you want to Sort anything using your own rules, you can implement a custom comparer (IComparer<T>), IComparer<IList<string>> in this particular case:

   public class MyListComparer : IComparer<IList<string>> {
      private static int CompareItems(string left, string right) {
        if (left.StartsWith("-"))
          if (right.StartsWith("-"))
            return -CompareItems(left.TrimStart('-'), right.TrimStart('-'));
          else
            return -1;
        else if (right.StartsWith("-"))
          return 1;

        left = left.TrimStart('0');
        right = right.TrimStart('0');  

        int result = left.Length.CompareTo(right.Length);

        if (result != 0)
          return result;

        for (int i = 0; i < left.Length; ++i) {
          result = left[i] - right[i];

          if (result != 0)
            return result;
        }

        return 0;
      }

      public int Compare(IList<string> x, IList<string> y) {
        if (ReferenceEquals(x, y))
          return 0;
        else if (null == x)
          return -1;
        else if (null == y)
          return 1;

        for (int i = 0; i < Math.Min(x.Count, y.Count); ++i) {
          int result = CompareItems(x[i], y[i]);

          if (result != 0)
            return result;
        }

        return x.Count.CompareTo(y.Count);
      }
    }

Then sort:

  var test = new List<List<string>>();

  test.Add(new List<string> { "1", "2", "3" });
  test.Add(new List<string> { "1", "4", "12" });
  test.Add(new List<string> { "1", "2", "9" });
  test.Add(new List<string> { "1", "4", "5" });
  test.Add(new List<string> { "6", "7", "8" });

  // Time to sort with a custom comparer
  test.Sort(new MyListComparer());

  string report = string.Join(Environment.NewLine, test
    .Select(line => string.Join(", ", line)));

  Console.Write(report);

Outcome:

  1, 2, 3
  1, 2, 9
  1, 4, 5
  1, 4, 12
  6, 7, 8

you can use the comparer with Linq query as well:

  var sorted = test.OrderBy(new MyListComparer());

Answer 3

There are two issues with your code. One is a syntax issue and one is a logic issue. To remove the compilation error you are seeing, the query variable must be an IOrderedQueryable instead of the IQueryable that you have listed. If you combine the query variable definition and initial ordering in to one line like below, your issue should resolve.

var query = test.AsQueryable().OrderBy(a => a[0]);

You could also use the IOrderedEnumerable instead using

var query = test.OrderBy(a => a[0]);

The logic issue is that your code will not produce the result you are expecting. You are ordering the list of the list of strings by its first value before ordering each list of strings. In other words, your initial Orderby needs to be below your for loop. For simplicity I'm simplifying to this Linq expression:

var sorted = test
    .Select(x => x.OrderBy(y => y).ToList())
    .OrderBy(x => x[0])
    .ToList();