Natural Sorting

Natural sorting of string values can be an issue that you as a developer will run into time from time. And if you haven't, you will. Recently I had to organise a list of filenames into their natural sort or human sort order. The filenames would appear as:

• Image1.jpg
• Image100.jpg
• Image2.jpg
• Image200.jpg
• Image3.jpg

And So on, instead of the nice natural sort order of

• Image1.jpg
• Image2.jpg
• Image3.jpg
• Image100.jpg
• Image200.jpg

and so on. To work around this issue we will need to create a custom compare function that allows Natural Sorting of string values.

public int compare(object x, object y)
{
    if (x == null && y == null)
    {
        return 1;
    }

    string s1 = x as string;
    string s2 = y as string;
    int marker1 = 0;
    int marker2 = 0;

    // Walk through two the strings with two markers.
    while (marker1 < len1 && marker2 < len2)
    {
        char ch1 = s1[marker1];
        char ch2 = s2[marker2];
        
        // Some buffers we can build up characters in for each chunk.
        char[] space1 = new char[len1];
        int loc1 = 0;
        char[] space2 = new char[len2];
        int loc2 = 0;
        
        // Walk through all following characters that are digits or
        // characters in BOTH strings starting at the appropriate marker.
        // Collect char arrays.
        do
        {
            space1[loc1++] = ch1;
            marker1++;
            if (marker1 < len1)
                {
                    ch1 = s1[marker1];
                }
                else
                {
                    break;
                }
            } while (char.IsDigit(ch1) == char.IsDigit(space1[0]));
            do
            {
                space2[loc2++] = ch2;
                marker2++;
                if (marker2 < len2)
                {
                    ch2 = s2[marker2];
                }
                else
                {
                    break;
                }
            } while (char.IsDigit(ch2) == char.IsDigit(space2[0]));
            // If we have collected numbers, compare them numerically.
            // Otherwise, if we have strings, compare them alphabetically.
            string str1 = new string(space1);
            string str2 = new string(space2);
            int result;
            if (char.IsDigit(space1[0]) && char.IsDigit(space2[0]))
            {
                int thisNumericChunk = int.Parse(str1);
                int thatNumericChunk = int.Parse(str2);
                result = thisNumericChunk.CompareTo(thatNumericChunk);
            }
            else
            {
                result = str1.CompareTo(str2);
            }
            if (result != 0)
            {
                return result;
            }
        }
        return len1 - len2;
    }

And viola! This will Naturally sort a given string array. The function has also been created as an implementation of ICompare interface. As such it can be employeed in classes that implementthe ICompare interface to get natural sorting.

Disclaimer: The content provided in this article is not warranted or guaranteed by rnddev. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts. As such it is inferred on to the reader to employ real-world tactics for security and implementation of best practices. I am not liable for any negative consequences that may result from implementing any information covered in this or other articles or blog posts.