Search code examples
c#stringsortingnatural-sort

Natural Sort Alpha-numeric like Windows Explorer in C#


I am looking for a natural sort technique like Windows explorer does.

For example, if I have the Alpha-numeric Array -

var array = new[]{"B01 002", "B01 0010", "01", "B01 001", "B10 001", "B01 01", "1", "B1 001", "B02 001", "A1"};

I am expecting this to be sorted in the below Order-
[01, 1, A1, B01 001, B01 01, B01 002, B01 0010, B1 001, B02 001, B10 001]

This is precisely the way that Windows Explorer does it-

enter image description here

I have tried the solutions in the below thread-

No other constraint on the approach taken. Either it is LINQ, Regex, Extention, or Interface approach that can be used to replicate the sort order done by "shlwapi.dll"


Solution

  • I suggest splitting string to chunks where each chunk is either all digits or no digits: "B01 001" -> {"B", "01", " ", "001"}. Then compare these chunks (comparing two all digits chunks being a special case).

    Code: (Fiddle)

    public sealed class NaturalComparer : IComparer<string> {
    
      private static int CompareChunks(string x, string y) {
        if (x[0] >= '0' && x[0] <= '9' && y[0] >= '0' && y[0] <= '9') {
          string tx = x.TrimStart('0');
          string ty = y.TrimStart('0');
    
          int result = tx.Length.CompareTo(ty.Length);
    
          if (result != 0)
            return result;
    
          result = tx.CompareTo(ty);
    
          if (result != 0)
            return result;
        }
        
        return string.Compare(x, y);
      }
    
      public int Compare(string? x, string? y) {
        if (ReferenceEquals(x, y))
          return 0;
        if (x is null)
          return -1;
        if (y is null)
          return +1;
    
        var itemsX = Regex
          .Split(x, "([0-9]+)")
          .Where(item => !string.IsNullOrEmpty(item))
          .ToList();
    
        var itemsY = Regex
          .Split(y, "([0-9]+)")
          .Where(item => !string.IsNullOrEmpty(item))
          .ToList();
    
        for (int i = 0; i < Math.Min(itemsX.Count, itemsY.Count); ++i) {
          int result = CompareChunks(itemsX[i], itemsY[i]);
    
          if (result != 0)
            return result;
        }
    
        return itemsX.Count.CompareTo(itemsY.Count);
      }
    }
    

    Demo:

    string[] demo = new string[] {
        "B01 002", 
        "B01 0010", 
        "01", 
        "B01 001", 
        "B10 001", 
        "B01 01", 
        "1", 
        "B1 001", 
        "B02 001", 
        "A1"
    };
    
    Array.Sort(demo, new NaturalComparer());
    
    Console.WriteLine(string.Join(Environment.NewLine, demo));
    

    Output:

    01
    1
    A1
    B01 001
    B01 01
    B01 002
    B01 0010
    B1 001
    B02 001
    B10 001