IOrderComparer unique ordering situation

Question

I am trying to order mixed strings in a unique way and am wondering if anyone else has done this. I have found several articles on using IOrderConparer but can not find a solution for my particular sorting problem.

I have the following:

1017, 650, 650C, 650B, W323, 10, 20, 1000, W1000

I need to order them as follows:

10, 20, 650, 650B, 650C, 1000, 1017, W323, W1000

Any help would be appreciated. Thanks.

Answer 1

Implement the compare using StrCmpLogicalW:

[DllImport("shlwapi.dll", CharSet = CharSet.Unicode)]
public static extern int StrCmpLogicalW(string x, string y);

This will do a logical (taking numbers into account) string compare rather then a standard string based one which will give you the result you are after.

Answer 2

A bit longer but all managed code

public class LogicalSorter : IComparer
{
    public int Compare(object a, object b)
    {
        var first = Regex.Split((string)a,"([0-9]+)").Where(s => s != "").ToArray();
        var second = Regex.Split((string)b,"([0-9]+)").Where(s => s != "").ToArray();

        var endIdx = Math.Min(first.Count(), second.Count());

        for (var i = 0; i < endIdx; i++)
        {
            var part1 = first.ElementAt(i);
            var part2 = second.ElementAt(i);

            if (part1.All(char.IsDigit) && part2.All(char.IsDigit) && part1 != part2)
            {
                return int.Parse(part1).CompareTo(int.Parse(part2));
            }

            if (part1 != part2) return part1.CompareTo(part2);
        }

        return first.Count().CompareTo(second.Count());
    }
}

Use it like this

string[] values = { "1017", "650", "650C", "650B", "W323", "10", "20", "1000", "W1000" };

Array.Sort(values, new LogicalSorter());

foreach (var value in values)
   Console.WriteLine(value);

Or using generics as suggested by Mrinal (preferred)

public class LogicalSorter : IComparer<String>
{
    public int Compare(String a, String b)
    {
        var first = Regex.Split(a, "([0-9]+)").Where(s => s != "").ToArray();
        var second = Regex.Split(b, "([0-9]+)").Where(s => s != "").ToArray();

        var endIdx = Math.Min(first.Count(), second.Count());

        for (var i = 0; i < endIdx; i++)
        {
            var part1 = first.ElementAt(i);
            var part2 = second.ElementAt(i);

            if (part1.All(char.IsDigit) && part2.All(char.IsDigit) && part1 != part2)
            {
                return int.Parse(part1).CompareTo(int.Parse(part2));
            }

            if (part1 != part2) return part1.CompareTo(part2);
        }

        return first.Count().CompareTo(second.Count());
    }
}

Example of optimized managed code (for speed not for looks), performs at 47x the regex version

public class LogicalSorter : IComparer<String>
{
    public int Compare(String a, String b)
    {
        var aLength = a.Length;
        var bLength = b.Length;
        var aIdx = 0;
        var bIdx = 0;
        int aPartLen;
        int bPartLen;
        int aPartEndIndex;
        int bPartEndIndex;
        bool aIsString;
        bool bIsString;

        // Examine both strings on character level, keep track of where
        // we are in each string since lengths might differ
        while (aIdx < aLength && bIdx < bLength)
        {
            // If both strings contain digit at current index
            // compare numbers
            if (char.IsDigit(a[aIdx]) && char.IsDigit(b[bIdx]))
            {
                // Get longest consecutive list of digits from each string
                aPartEndIndex = aIdx;
                while (aPartEndIndex < aLength && char.IsDigit(a[aPartEndIndex])) { aPartEndIndex++; }

                bPartEndIndex = bIdx;
                while (bPartEndIndex < bLength && char.IsDigit(b[bPartEndIndex])) { bPartEndIndex++; }

                aPartLen = aPartEndIndex - aIdx;
                bPartLen = bPartEndIndex - bIdx;

                // Compare lengths (longest number is greater)
                if (aPartLen != bPartLen) return aPartLen < bPartLen ? -1 : 1;

                // Same length numbers, compare chars until not same or end
                while (aIdx < aPartEndIndex && a[aIdx] == b[bIdx])
                {
                    aIdx++;
                    bIdx++;
                }

                // If not at end compare last characters that were not same
                if(aIdx != aPartEndIndex)
                    return a[aIdx] < b[bIdx] ? -1 : 1;
            }
            else
            {
                // Comparing string vs number or string vs string
                aIsString = char.IsLetter(a[aIdx]);
                bIsString = char.IsLetter(b[bIdx]);

                // if not 2 strings, number is always first
                if (aIsString != bIsString) return aIsString ? 1 : -1;

                // Get longest consecutive list of letters from each string
                aPartEndIndex = aIdx;
                while (aPartEndIndex < aLength && (char.IsLetter(a[aPartEndIndex]) == aIsString))
                {
                    aPartEndIndex++;
                }

                bPartEndIndex = bIdx;
                while (bPartEndIndex < bLength && (char.IsLetter(b[bPartEndIndex]) == bIsString))
                {
                    bPartEndIndex++;
                }

                // Compare chars until not same or end
                while (aIdx < aPartEndIndex && bIdx < bPartEndIndex && a[aIdx] == b[bIdx])
                {
                    aIdx++;
                    bIdx++;
                }

                // if not at end compare last letters found
                if ((aIdx != aPartEndIndex) || (bIdx != bPartEndIndex))
                    return a[aIdx] < b[bIdx] ? -1 : 1;
            }
        }

        // Use length as tie breaker
        return aLength < bLength ? -1 : 1;
    }
}