Natural Sorting Issue

Question

I have been trying to use the code borrowed from here to sort out a collection of a custom object with my application. Generally the sorting works fine until i encounter the following strings

D-016.0,
D-016.,
D-016.00,
D-016.000 001,
D-016.000 002,
D-016.000,
D-016.00 003,
D-016.00 002,
D-016. 001,
D-016. 002,
D-016.0 001,
D-016.00 001

which for some very odd reason returns the collection in the order

D-016.00,
D-016.000,
D-016.0,
D-016.000 001,
D-016. 001,
D-016.0 001,
D-016.00 001,
D-016.00 002,
D-016.000 002,
D-016. 002,
D-016.00 003,
D-016.

The collection i am expecting to see would look as Windows Explorer would show which should be

D-016. 001,
D-016. 002,
D-016.,
D-016.000 001,
D-016.000 002,
D-016.000,
D-016.00 001,
D-016.00 002,
D-016.00 003,
D-016.00,
D-016.0 001,
D-016.0,

Following the suggestion from the Natural Sort Order in C# posted by Michael Kniskern, i tried to implement the answer which uses shlwapi.dll and this return the order i i would expect to see it as per the last collection listed above. However this approach only works in Windows 7 and return an uneven collection in Windows XP.

I suspect that files that are listed as D-016.00, D-016.0 and D-016.000 would get they list of 0s concatenated when parsing to int which would result in this error. However i cannot understand exactly how exactly to fix this (too new to these comparer interfaces). Can anyone please suggest a solution for this?

Below is the code that i am currently using

public class NaturalSorter<T> : IComparer<string>, IDisposable
{
    private readonly bool ascending;
    private Dictionary<string, string[]> table = new Dictionary<string, string[]>();


    public NaturalSorter(bool inAscendingOrder = true)
    {
        ascending = inAscendingOrder;
    }

    #region IComparer Members


    public int Compare(string[] x, string[] y)
    {
        throw new NotImplementedException();
    }

    #endregion

    #region IComparer Members

    int IComparer<string>.Compare(string x, string y)
    {
        if (x == y)
            return 0;

        string[] x1, y1;

        if (!table.TryGetValue(x, out x1))
        {
            x1 = Regex.Split(x.Replace(" ", ""), "([0-9]+)");
            table.Add(x, x1);
        }

        if (!table.TryGetValue(y, out y1))
        {
            y1 = Regex.Split(y.Replace(" ", ""), "([0-9]+)");
            table.Add(y, y1);
        }

        int returnVal = 0;

        for (int i = 0; i < x1.Length && i < y1.Length; i++)
        {
            if (x1[i] != y1[i])
            {
                returnVal = PartCompare(x1[i], y1[i]);
                return ascending ? returnVal : -returnVal;
            }
        }

        if (y1.Length > x1.Length)
        {
            returnVal = 1;
        }
        else if (x1.Length > y1.Length)
        {
            returnVal = -1;
        }
        else
        {
            returnVal = 0;
        }

        return ascending ? returnVal : -returnVal;
    }

    private static int PartCompare(string left, string right)
    {
        int x, y;
        if (!int.TryParse(left, out x))
            return left.CompareTo(right);

        if (!int.TryParse(right, out y))
            return left.CompareTo(right);

        return x.CompareTo(y);
    }

    #endregion

    public void Dispose()
    {
        table.Clear();
        table = null;
    }
}

Natural sort order and Windows Explorer sort order are not the same. Windows Explorer has special handling, because it treats the part after the last dot as the file extension if it doesn't start with a space. That results in a different ordering. — Daniel Hilgarth, Jan 29 '13 at 16:37
You don't need to use fancy natural sorting algorithms if your numbers are zero padded, as they appear to be here. Further, I can't seem to identify the criteria by which you obtained your expected sort order. I would expect `D-016., D-016. 001, D-016. 002, D-016.0, ...` — JosephHirn, Jan 29 '13 at 16:57

score 0 · Answer 1 · answered Jan 29 '13 at 16:55

This is the best I could come up with:

Replace the splitting with:

if (!table.TryGetValue(x, out x1))
{
    x1 = Regex.Split(x, @"([0-9]+|\.)");
    table.Add(x, x1);
}

if (!table.TryGetValue(y, out y1))
{
    y1 = Regex.Split(y, @"([0-9]+|\.)");
    table.Add(y, y1);
}

And add the following to the top of PartCompare()

private static int PartCompare(string left, string right)
{
     if (left.Length > right.Length) return -1;
     else if (left.Length < right.Length) return 1;

     int x, y;
     ...

This produces:

D-016. 001,
D-016. 002,
D-016.000 001,
D-016.000 002,
D-016.000,
D-016.00 001,
D-016.00 002,
D-016.00 003,
D-016.00,
D-016.0 001,
D-016.0,
D-016.,  // The one out-of-order item.

Natural Sorting Issue

1 Answers1