LINQ: OrderBy with Complex Sort Key

Introduction

This is an alternative to the original tip[^]. While that original tip shows a fully hand-crafted version of sorting an array by a complex sort key, I show here a LINQ based approach, based on the IComparer<T> interface.

The Complex Sort Criteria

The OP defined quite a complex sort criteria which I try to summarize more formally:

1. strings with capital letters come before strings without capital letters
2. with the character position of the first capital letter in a string: smaller index comes first
3. if same index: sorting is given in lexicographical order[^] of that respective capital letter
4. if same capital letter or no capital letter contained in the element string: sorting is given by the original strings, case insensitive

Now that we have the sort criteria, let's look at the code.

The Code

I'd like to call the code as given by the OP, but with the LINQ OrderBy(...)[^] extension method overload that takes a key generator plus an IComparer of such keys.

The application of the code shall be as follows:

public static void Main()
{
    string[] data = { "wZa", "wwwWa", "wbwwwa", "wWe", "sSsssssw", 
                      "Aww", "abwqA","aXcd","kolkataKnight","aXcD" };
    foreach (var item in data.OrderBy(Cmp.Key, Cmp.Default))
    {
        Console.WriteLine(item);
    }
}

With the OP provided data, the output is

Aww
sSsssssw
wWe
aXcd
aXcD
wZa
wwwWa
abwqA
kolkataKnight
wbwwwa

The Cmp Class

The OrderBy(...) method takes a key generator delegate plus an IComparer<T>[^] instance for comparing the keys.

Here goes the class:

class Cmp : IComparer<Tuple<int, char, string>>
{
    // get the one and only instance
    public static readonly Cmp Default = new Cmp();
    // generate a key from an element:
    // - Item1 = position of first capital letter (or int.MaxValue if none)
    // - Item2 = capital letter (or space character if no capital letter given)
    // - Item3 = original string as lower letter string
    public static Tuple<int, char, string> Key(string s)
    {
        // get the position of the first upper case letter or -1 if there is no such letter
        int pos = (s.Select((c,i)=>char.IsUpper(c) ? i+1 : 0) // IsUpper then (pos+1), else (0)
                    .FirstOrDefault(i=>i>0)                   // get first that is not (0)
                    )-1;                                      // fix-back offset of (pos+1)
        return pos < 0
            ? new Tuple<int, char, string>(int.MaxValue, ' ', s.ToLower()) // lower case only strings
            : new Tuple<int, char, string>(pos, s[pos], s.ToLower());      // at least one upper case
    }
    // IComparer implementation:
    // - 1st = position of first capital letter
    // - 2nd = capital letter
    // - 3rd = case insensitive original string
    public int Compare(Tuple<int, char, string> x, Tuple<int, char, string> y)
    {
        int res = x.Item1.CompareTo(y.Item1); // sort first by first upper letter pos
        if (res == 0) res = x.Item2.CompareTo(y.Item2); // second by upper letter
        if (res == 0) res = x.Item3.CompareTo(y.Item3); // then by the string itself (case insensitive)
        return res;
    }
}

Key features:

• The key consists of three parts, implemented by a Tuple[^] class.
• The three items of the key represent the three sort criteria: position, capital letter, element string as lower case.
• To achieve the 1^st criterion, strings with only lower letters have the "capital letter position" set to int.MaxValue, leading to the correct sort constraint for these cases.
• The IComparer<T> implementation of the Compare method is straight forward with this key: compare the 1^st criterion, if equal go to the 2^nd, if that is still equal, take the last one.

Performance considerations are not made, i.e., this complex sorting may not be so suitable for huge data lots, but for reasonably sized collections, it may be sufficient.

History

• V1.0, 2012-06-05: Initial version