自然なソート順序

突然ですが、Windowsのエクスプローラーのソートってなかなか気が利くと思いません？

ファイル名でソートを掛けると、上記の画像のような順に並び変わります。
それでは、これを通常のソートを掛けるとどうなるでしょう。

foreach(var s in new[] { "test01.txt", "test1.txt", "test3.txt", "test10.txt", }.OrderBy(p => p))
    Console.WriteLine(s);

あれ？エクスプローラーだとtest10.txtよりtest3.txtのほうが前に来ていたけどC#のOrderByだと逆転しているぞ？バグかな？

そんなことはありません。
OrderByは文字列を辞書順に並び替えます。もっと正確に言えば、文字コードの若い順から辞書順に並び替えます。ですので、1文字ずつ文字コードを比較していって、test10.txtの1とtest3.txtの3を見て、前者のほうが若番なので辞書的に前だと判断しているのです。

ですが、実際にファイル名を並び替えた人からしたらtest3.txtとtest10.txtは前者のほうが前に来てほしいですよね。これが「Natural Sort Order（自然なソート順序）」です。


さて、このようなソートをする方法ですが、ググるといろいろな方法が出てきます。丸投げしたいのならば、Nugetを漁ったりStrCmpLogicalW関数をP/Invokeで使うのも手でしょう。ですが、私はあまり気に入った実装が無かったので自分で実装してみることにしました。

まずは下準備として、文字列を数字と文字の境界で区切るメソッドを作ります。

internal static IEnumerable<string> SplitBy(this string Source, Func<char, char, bool> BorderSelector)
{
    int start = 0;
    for(int i = 0; i < (Source.Length - 1); i++) {
        if(BorderSelector(Source[i], Source[i + 1])) {
            yield return Source.Substring(start, i + 1 - start);
            start = i + 1;
        }
    }
    yield return Source.Substring(start, Source.Length - start);                
}

文字列の前後2文字を渡して境界かどうかを判定するデリゲートを渡せば、そこで区切った文字列を返してくれます。ちゃんと遅延評価も行えるように気を配って実装しました。
これを使って、IComparer<string>を実装します。

public class NaturalComparer : IComparer<string>, System.Collections.IComparer
{
    static Func<char, char, bool> NumberCharBorder = (p, n) => (('0' <= p && p <= '9') && !('0' <= n && n <= '9')) || (!('0' <= p && p <= '9') && ('0' <= n && n <= '9'));

    public int Compare(string x, string y)
    {
        using(var xe = x.SplitBy(NumberCharBorder).GetEnumerator())
        using(var ye = y.SplitBy(NumberCharBorder).GetEnumerator()) {
            while(true) {
                var xHasNext = xe.MoveNext();
                var yHasNext = ye.MoveNext();

                if(xHasNext && yHasNext) {
                    int ret = (ulong.TryParse(xe.Current, out ulong xi) && ulong.TryParse(ye.Current, out ulong yi)) ?
                        Comparer<ulong>.Default.Compare(xi, yi) :
                        Comparer<string>.Default.Compare(xe.Current, ye.Current);

                    if(ret != 0) return ret;
                } else
                    return (xHasNext ? 1 : 0) - (yHasNext ? 1 : 0);
            }
        }
    }

    int System.Collections.IComparer.Compare(object x, object y)
    {
        try {
            return Compare((string)x, (string)y);
        }
        catch(InvalidCastException e) {
            throw new ArgumentException(e.Message);
        }
    }

    public static NaturalComparer Default
    {
        get
        {
            if(_Default == null)
                _Default = new NaturalComparer();
            return _Default;
        }
    }
    static NaturalComparer _Default = null;
}

xとyを先ほどのSplitByで分割し、それを同時に列挙していっています。
MoveNext()とCurrentを自前で呼ぶのはできれば避けたかったのですが、 例えばZipで同時に列挙すると、xとyの分割したときの長さが分からなくなってしまうので、やむを得ず手動で列挙することにしました。
分割さえできれば後は簡単です。分割項が両方とも数字(ulong)として読めるならば数字として比較し、それ以外なら文字列として比較します。比較結果が一致しなかったら、その大小関係を返し、一致したら次の分割項へと移っていきます。分割項が片側無くなった場合は、まだ残っているほう（元の文字列が長いほう）を大として返します。

 絵にするとこんな感じです。文字列（青線）と数字（橙線）に分け、それぞれで大小比較をします。例2のように片側がすでに末尾に達して、もう片側は末尾に達していなかった場合は、後者を大としています。

C#のLINQのOrderByにはIComparer<T>を受け取るオーバーロードがあるので、これに渡してあげればこの自然順ソートができます。
が、せっかくなので、親切に拡張メソッドも作っておいてあげましょう。

public static IOrderedEnumerable<T> NaturallyOrderBy<T>(this IEnumerable<T> Source, Func<T, string> KeySelector)
{
    return Source.OrderBy(KeySelector, NaturalComparer.Default);
}

public static IOrderedEnumerable<string> NaturallyOrderBy(this IEnumerable<string> Source)
{
    return Source.OrderBy(p => p, NaturalComparer.Default);
}

public static IOrderedEnumerable<T> NaturallyOrderByDescending<T>(this IEnumerable<T> Source, Func<T, string> KeySelector)
{
    return Source.OrderByDescending(KeySelector, NaturalComparer.Default);
}

public static IOrderedEnumerable<string> NaturallyOrderByDescending(this IEnumerable<string> Source)
{
    return Source.OrderByDescending(p => p, NaturalComparer.Default);
}

public static IOrderedEnumerable<T> NaturallyThenBy<T>(this IOrderedEnumerable<T> Source, Func<T, string> KeySelector)
{
    return Source.ThenBy(KeySelector, NaturalComparer.Default);
}

public static IOrderedEnumerable<string> NaturallyThenBy(this IOrderedEnumerable<string> Source)
{
    return Source.ThenBy(p => p, NaturalComparer.Default);
}

public static IOrderedEnumerable<T> NaturallyThenByDescending<T>(this IOrderedEnumerable<T> Source, Func<T, string> KeySelector)
{
    return Source.ThenByDescending(KeySelector, NaturalComparer.Default);
}

public static IOrderedEnumerable<string> NaturallyThenByDescending(this IOrderedEnumerable<string> Source)
{
    return Source.ThenByDescending(p => p, NaturalComparer.Default);
}

単純にOrderByなどのメソッドをラップしているだけです。このNaturallyOrderByにはstringの配列を渡すことが圧倒的に多いはずですので、KeySelectorを省略できるオーバーロードも用意してあげました。

今回のこのプログラムでは正規表現も使っていませんし、比較時の列挙も1回きりです。相当なパフォーマンスで動作してくれると思います。
これで、自分の作るソフトの中でも自然順ソートを気軽に使えるようになりました。



余談1
Windowsエクスプローラーがこのソート順序に対応したのはXPくらいからだったと思います。少なくともWindows98のときは対応しておらず、ちゃんとファイル名の数字の桁数をそろえて（桁数が少ないものは0埋めして）やらないとソートできなかった記憶があります。
StrCmpLogicalWがあってもStrCmpLogicalAが無いことからしても、Windows 9x系統では実装されていなかったんでしょうね。

余談2
英語圏の人が思いつく「自然なソート順序」はこれくらいかもしれませんが、日本語圏にいると「全角/半角を区別せずにソート」とか「漢数字も数字としてソート」とかいろいろ思いつくと思います。
もっと極端な例を言えば「前編」「後編」が付くファイル名があれば「前編」のほうが前に来てほしいですが、文字コードでは前>後です（おそらく音読みの「ゼン」「コウ」で五十音順に並べているため）のでそのようにはなりません。ただ、前原さんと後藤さんだったら後藤さんのほうが前に来てほしいですし、単純に「前」を前に持ってくればいいというわけでもありません。
そういう意味からしても「自然なソート順序」というのは非常に曖昧な定義で、網羅的に実装するのには無理があるでしょう。どこで決着をつけるかはプログラマーのさじ加減かと思います。