[C#] 文字列を数値の大きさで並び替える自然ソートを行う

C# C# Win32API
2022-12-04 (日)

Windows エクスプローラーのファイル順と同じように、文字列中の数字を値の大きさでソートします。OS に依存しない実装も対応します。

環境

  • .NET 6.0.10 (SDK 6.0.402)
  • C# 10.0
  • Visual Studio 2022 Version 17.3.6
  • Windows 10 Pro 64bit 22H2 19045.2251

結果

1. Windows 用: エクスプローラーと同じ並び順 (Win32 API)

Win32 API StrCmpLogicalW() を使用します。数値部分を値比較するように自然ソートになりますが、仕様が特殊のようです (後述)。

using System.Runtime.InteropServices;

public class NaturalStringComparer : IComparer<string?>
{
    public static IComparer<string?> Windows { get; } = new NaturalStringComparer();

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

    private NaturalStringComparer()
    {
    }

    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;

        return StrCmpLogicalW(x, y);
    }
}

使用例

// Array
var array = new[] { "name1", "name2", "name01" };
Array.Sort(array, NaturalStringComparer.Windows);

// List
var list = new List<string> { "name1", "name2", "name01" };
list.Sort(NaturalStringComparer.Windows);

// LINQ
var enumerable = new[] { "name1", "name2", "name01" };
var sortedArray = enumerable.OrderBy(x => x, NaturalStringComparer.Windows).ToArray();

2. Win32 API を使用しない版 (仮実装)

1 の StrCmpLogicalW() は

  • Windows 限定 (Win32 API)
  • 大文字と小文字を区別しない

のような課題があるので、依存しない形で実装してみます。

使用例

var array = new[] { "name1", "name2", "name01" };
Array.Sort(array, NaturalStringComparer.Ordinal);

特徴

  • StrCmpLogicalW() と同じような並び順になるように努力。
  • null を正しく比較する (後述1)。
  • 大文字と小文字も区別して並び替え (後述2)。
  • string.Substrings() などは使用せず、文字列のアロケーションなし。
  • NaturalStringComparer.Ordinal などで static インスタンスを共有可能。

⚠️ ただし、中途半端な実装コードなので、全く同じ並び順にはならないことに注意してください。

public static class NaturalStringComparer
{
    public static IComparer<string?> Windows { get; } = new WindowsComparer();
    public static IComparer<string?> Ordinal { get; } = new DefaultComparer(StringComparison.Ordinal);
    public static IComparer<string?> OrdinalIgnoreCase { get; } = new DefaultComparer(StringComparison.OrdinalIgnoreCase);

    private class WindowsComparer : IComparer<string?>
    {
        [DllImport("shlwapi.dll", CharSet = CharSet.Unicode, ExactSpelling = true)]
        private static extern int StrCmpLogicalW(string x, string 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;

            return StrCmpLogicalW(x, y);
        }
    }

    private class DefaultComparer : IComparer<string?>
    {
        private const char IgnoreChar = '-';

        // Token values (not an enum as a performance micro-optimization)
        private static class Token
        {
            internal const byte None = 0;
            internal const byte Ignore = 1;
            internal const byte OtherPunctuation = 2;
            internal const byte MathSymbol = 3;
            internal const byte Other = 2;
            internal const byte Digits = 4;
            internal const byte Number = 5;
            internal const byte Letters = 6;
        }

        private readonly StringComparison _stringComparison;

        internal DefaultComparer(StringComparison stringComparison)
        {
            _stringComparison = stringComparison;
        }

        public int Compare(string? str1, string? str2)
        {
            if (ReferenceEquals(str1, str2)) return 0;
            if (str1 is null) return -1;
            if (str2 is null) return 1;

            var nextStartIndex1 = 0;
            var nextStartIndex2 = 0;

            while (true)
            {
                // token
                var (token1, startIndex1, length1) = GetNextToken(str1, nextStartIndex1);
                var (token2, startIndex2, length2) = GetNextToken(str2, nextStartIndex2);

                var tokenCompare = token1.CompareTo(token2);
                if (tokenCompare != 0)
                    return tokenCompare;

                if (token1 == Token.None)
                    return str1.Length.CompareTo(str2.Length);

                if (token1 == Token.Digits)
                {
                    // '0' pad left
                    var maxLength = Math.Max(length1, length2);
                    var paddingLength1 = maxLength - length1;
                    var paddingLength2 = maxLength - length2;

                    for (var i = 0; i < maxLength; i++)
                    {
                        var digit1 = i < paddingLength1 || str1[startIndex1 + i - paddingLength1] == IgnoreChar ? 0 : CharUnicodeInfo.GetNumericValue(str1[startIndex1 + i - paddingLength1]);
                        var digit2 = i < paddingLength2 || str2[startIndex2 + i - paddingLength2] == IgnoreChar ? 0 : CharUnicodeInfo.GetNumericValue(str2[startIndex2 + i - paddingLength2]);

                        var digitCompare = digit1.CompareTo(digit2);
                        if (digitCompare != 0)
                            return digitCompare;
                    }

                    var paddingCompare = paddingLength1.CompareTo(paddingLength2);
                    if (paddingCompare != 0)
                        return paddingCompare;
                }
                else
                {
                    var minLength = Math.Min(length1, length2);
                    var compare = string.Compare(str1, startIndex1, str2, startIndex2, minLength, _stringComparison);
                    if (compare == 0)
                    {
                        compare = length1 - length2;
                    }

                    if (compare != 0)
                        return compare;
                }

                nextStartIndex1 += length1;
                nextStartIndex2 += length2;
            }
        }

        private static (byte token, int startIndex, int length) GetNextToken(string str, int startIndex)
        {
            if (startIndex >= str.Length)
            {
                return (Token.None, -1, 0);
            }

            // - があれば無視して、次の文字を採用する
            // ただし、文末まで - の場合は、- としてソート先頭にする
            if (str[startIndex] == IgnoreChar)
            {
                for (var i = startIndex + 1; i < str.Length; i++)
                {
                    if (str[i] != IgnoreChar)
                    {
                        // - 以外の文字があったので、- を無視して次の文字で判定する
                        return GetNextToken(str, i);
                    }
                }

                // 全て - で構成されていた場合
                return (Token.Ignore, startIndex, str.Length - startIndex);
            }

            // 次の文字が - で始まらない場合
            var token = GetTokenFromChar(str[startIndex]);
            var length = 1;
            for (var i = startIndex + 1; i < str.Length; i++)
            {
                var charToken = GetTokenFromChar(str[i]);

                if (token != charToken)
                {
                    break;
                }

                length++;
            }

            // 半角/全角は数値として比較する
            // ただし、半角/全角が異なるところを区切りにして比較するので、Token は Digits と TokenNumber で分けている
            if (token == Token.Number)
                token = Token.Digits;

            return (token, startIndex, length);
        }

        // 仮実装 (カスタマイズの余地あり)
        private static byte GetTokenFromChar(char c)
        {
            if (c is >= '0' and <= '9') return Token.Digits;
            if (char.IsNumber(c)) return Token.Number;
            if (char.IsLetter(c)) return Token.Letters;

            return CharUnicodeInfo.GetUnicodeCategory(c) switch
            {
                UnicodeCategory.MathSymbol => Token.MathSymbol,
                UnicodeCategory.OtherPunctuation => Token.OtherPunctuation,
                _ => Token.Other,
            };
        }
    }
}

3. NaturalSort.Extension (NuGet)

NuGet にある中で一番良さそうです。

特徴

  • ✅ .NET 6.0, .NET Standard 1.3 対応
  • ✅ TryParse() などのパース処理なし。
  • ✅ 数字が大量に連続していても比較可能 (long.MaxValue を超えた数値でも1文字ずつ比較するので問題なし)。
  • ✅ StringComparison を指定すれば、文字列のアロケーション無し。
  • ⚠️ StringComparer (StringComparer.Ordinal も含む) を指定した場合は、string.Substrings() によるアロケーションが発生する。
  • ⚠️ WithNaturalSort() を使用すると、NaturalSortComparer のアロケーションが発生する。

4. 日本語を考慮した自然ソート

漢数字、ローマ数字、半角全角、前中後・上中下などの並び順まで対応されています。

さらに、バグが修正されているコードのようです。

StrCmpLogicalW の不具合

Windows のバージョンにより結果が異なり、古い Windows (XP, Vista あたり) の時代だとバグがあったらしい。

StrCmpLogicalW の注意点と特徴

StrCmpLogicalW() を使用していて、気付いた特徴と注意点を記載しておきます。
色々と複雑な判定を行っていそうなソートに見えます。

1. null 比較は正しくない

まず、一番大事と思われる注意点です。

null を比較対象に含むと、常に -2 が返されてしまいます。

// "" は正しく 0 になる
StrCmpLogicalW("", "");     // 0

// どちらかに null を含むと、常に -2 になってしまう
StrCmpLogicalW(null, null); // -2
StrCmpLogicalW(null, "");   // -2
StrCmpLogicalW("", null);   // -2

本来 C# の判定では、null 同士なら等しく、片方が null の場合は null の方が小さい値としてみなされます。
string.CompareOrdinal() の注釈を参考。

// null 同士でも同じ値なら正しく 0 になる
string.CompareOrdinal.Compare("", "");     // 0
string.CompareOrdinal.Compare(null, null); // 0

// どちらかが null だと null の方が小さい値と判定される
string.CompareOrdinal.Compare(null, "");   // -1
string.CompareOrdinal.Compare("", null);   // 1

null を考慮した比較にしたいので、以下のように実装しました。

public int Compare(string? x, string? y)
{
    // null を考慮した正しい比較をする
    if (ReferenceEquals(x, y)) return 0;
    if (x is null) return -1;
    if (y is null) return 1;

    // 両方が null ではない場合の比較をする
    return StrCmpLogicalW(x, y);
}

ただ、StrCmpLogicalW() をファイル名のソートで使用するなら問題ありません。
ファイル名が null のファイルは作成自体できないため、存在すらありえないためです。

2. 大文字、小文字は区別しない

StrCmpLogicalW() は OrdinalIgnoreCase と同様に、大文字と小文字を区別せずに等しいと判定されてしまいます。

// 大文字と小文字を区別しないので、等しいと判定されるので 0 となる
StrCmpLogicalW("a", "A");                           // 0
StringComparer.OrdinalIgnoreCase.Compare("a", "A"); // 0

// Ordinal では、大文字と小文字を区別するので 0 ではない
StringComparer.Ordinal.Compare("a", "A");           // 32

例えば、大文字と小文字の違いで同じ名前を含む場合のソートは以下のようになります。

// 大文字と小文字の違いで、同じ名前がある場合のソート
var array = new[] { "name", "NAME", "name" };

// 1. StrCmpLogicalW
Array.Sort(array, NaturalStringComparer.Windows);
// 2. OrdinalIgnoreCase
Array.Sort(array, StringComparer.OrdinalIgnoreCase);
// 3. Ordinal
Array.Sort(array, StringComparer.Ordinal);

StrCmpLogicalW() は、name が1番目と3番目に並んでしまいます。
Ordinal は、小文字の name が連続で並びます。

入力文字列1. StrCmpLogicalW2. OrdinalIgnoreCase3. Ordinal
namenamenameNAME
NAMENAMENAMEname
namenamenamename

ただ、StrCmpLogicalW() をファイル名のソートで使用するなら問題ありません。
ファイルは大文字と小文字を区別しないため、そもそも大文字と小文字の違いで同名のファイルは作成できないためです。

3. 数値は整数として比較され、小数点は考慮されない

まずは、整数でソートした場合です。

var array = new[] { "02", "01", "10", "2", "1" };

Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);

StrCmpLogicalW() では、整数の大きさで並び替わります。
Ordinal は、文字列順です。

入力文字列1. StrCmpLogicalW()2. Ordinal
020101
01102
10021
2210
1102

次に、小数点を含めてソートした場合です。

var array = new[] { "1.02", "1.01", "1.10", "1.2", "1.1" };

Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
入力文字列1. StrCmpLogicalW()2. Ordinal
1.021.011.01
1.011.11.02
1.101.021.1
1.21.21.10
1.11.101.2

StrCmpLogicalW() は . で区切り、小数点以下の部分のみを整数として比較しています。
小数点以下の部分のソート結果は 01, 1, 02, 2, 10 の順になります。

IP アドレスのように ###.###.###.### の形式でソートした場合、
. で区切り、それぞれの数値の大きさでソートされるようになります。

4. 連続のハイフンは1文字として扱われる

1文字のハイフンで検証

小数点の例と同じコードを、. ではなく - 区切りでソートした場合です。

var array = new[] { "1-02", "1-01", "1-10", "1-2", "1-1" };

Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
入力文字列1. StrCmpLogicalW()2. Ordinal
1-021-011-01
1-011-11-02
1-101-021-1
1-21-21-10
1-11-101-2

- 区切りでも、. 区切りの時と同じ結果です。

複数のハイフンで検証

ここで - の数を増やしてみます。

var array = new[] { "1-02", "1----01", "1--10", "1-----2", "1---1" };

Array.Sort(array, NaturalStringComparer.Windows);
Array.Sort(array, StringComparer.Ordinal);
入力文字列1. StrCmpLogicalW()2. Ordinal
1-021----011-----2
1----011---11----01
1--101-021---1
1-----21-----21--10
1---11--101-02

StrCmpLogicalW() は、. 区切りの時と同じ結果です。
- が複数個あっても、- 1個の時と同じ結果です。

Ordinal は、- の数が多い方が先にソートされます。
数字(0-9)より - の方が小さい文字と判定されるため、先にソートされます。

感謝

Issue

Wiki

NuGet (.NET 6 対応)

NuGet (.NET 5 対応) unsafe 使用, int で数値比較

NuGet (割当なしの比較、0パディングなしで比較)

GitHub

日本語記事

日本語に対応した実装

StrCmpLogicalW() 使用

StrCmpLogicalW() を使用しない実装

Win32

Stack Overflow
sorting - Natural Sort Order in C# - Stack Overflow

Unity

他言語

C# C# Win32API
2022-12-04 (日)
[Hugo] コードブロックをコピーするボタンを配置する
[C#] COM Object から TypeInfoName を取得する

関連記事

新着記事