.NETプログラミング研究/111 のバックアップ差分(No.2)

バックアップ一覧
現在との差分を表示
ソースを表示
バックアップを表示
.NETプログラミング研究/111 へ行く。
- 1 (2013-10-30 (水) 02:12:12)
- 2 (2013-10-30 (水) 02:12:12)
追加された行はこの色です。
削除された行はこの色です。
#title(エクスプローラのファイル順のように、自然順ソートで並び替える)

#navi(.NETプログラミング研究)

#contents

*エクスプローラのファイル順のように、自然順ソートで並び替える [#i2cfc97d]

例えば、文字列の配列

-img2.jpg
-img1.jpg
-img10.jpg

があった時、これを通常の方法（「[[配列やコレクション内の要素を並び替える>http://dobon.net/vb/dotnet/programing/icomparer.html]]」で紹介しているような方法）で並び替えると、
があった時、これを通常の方法（「[[配列やコレクション内の要素を並び替える>https://dobon.net/vb/dotnet/programing/icomparer.html]]」で紹介しているような方法）で並び替えると、

-img1.jpg
-img10.jpg
-img2.jpg

という順番になります。しかしエクスプローラでこのような名前のファイルを並び替えると、

-img1.jpg
-img2.jpg
-img10.jpg

のようになります。ファイルの並び方としては、この方がずっと分かりやすいです。

ここでは、このように自然順ソート（Natural Sort）で文字列の配列を並び替える方法を紹介します。

なお配列を並び替える方法についてはほとんど説明しませんので、分からない場合は、まず「[[配列やコレクション内の要素を並び替える>http://dobon.net/vb/dotnet/programing/icomparer.html]]」をご覧ください。
なお配列を並び替える方法についてはほとんど説明しませんので、分からない場合は、まず「[[配列やコレクション内の要素を並び替える>https://dobon.net/vb/dotnet/programing/icomparer.html]]」をご覧ください。

また、ここで紹介しているコードは、作成とテストに十分な時間をかけることができていないことをご了承ください。

**StrCmpLogicalWを使用する方法 [#n82e2788]

[[StrCmpLogicalW function>http://msdn.microsoft.com/en-us/library/windows/desktop/bb759947.aspx]]を使うと、エクスプローラと同じ並び順の並び替えができるようになるようです。

StrCmpLogicalWは、Windows XP以上で使用できます。また、WindowsのバージョンによってStrCmpLogicalWの結果が異なる可能性があります。

さらに「[[sorting - Natural Sort Order in C# - Stack Overflow>http://stackoverflow.com/questions/248603/natural-sort-order-in-c-sharp]]」にある書き込みによると、StrCmpLogicalWは推移的ではない（つまり、例えば文字列 a, b, c があって、a < b、 b < c なのに、a > c になることがある）ため、これを使って並べ替えを行うと無限ループになることがあるということです。

StrCmpLogicalWを使用して文字列を比較する、IComparerを実装したクラスの例を以下に示します。

#code(vbnet){{
''' <summary>
''' 大文字小文字を区別せずに、
''' 文字列内に含まれている数字を考慮して文字列を比較します。
''' </summary>
Public Class LogicalStringComparer
    Implements System.Collections.IComparer
    Implements System.Collections.Generic.IComparer(Of String)

    <System.Runtime.InteropServices.DllImport("shlwapi.dll", _
        CharSet:=System.Runtime.InteropServices.CharSet.Unicode, _
        ExactSpelling:=True)> _
    Private Shared Function StrCmpLogicalW(x As String, y As String) As Integer
    End Function

    Public Function Compare(x As String, y As String) As Integer _
        Implements System.Collections.Generic.IComparer(Of String).Compare
        Return StrCmpLogicalW(x, y)
    End Function

    Public Function Compare(x As Object, y As Object) As Integer _
        Implements System.Collections.IComparer.Compare
        Return Me.Compare(x.ToString(), y.ToString())
    End Function
End Class
}}

#code(csharp){{
using System;

/// <summary>
/// 大文字小文字を区別せずに、
/// 文字列内に含まれている数字を考慮して文字列を比較します。
/// </summary>
public class LogicalStringComparer :
    System.Collections.IComparer,
    System.Collections.Generic.IComparer<string>
{
    [System.Runtime.InteropServices.DllImport("shlwapi.dll",
        CharSet = System.Runtime.InteropServices.CharSet.Unicode,
        ExactSpelling = true)]
    private static extern int StrCmpLogicalW(string x, string y);

    public int Compare(string x, string y)
    {
        return StrCmpLogicalW(x, y);
    }

    public int Compare(object x, object y)
    {
        return this.Compare(x.ToString(), y.ToString());
    }
}
}}

これを使って実際に並び替えを行う例を以下に示します。

#code(vbnet){{
'並び替える文字列の配列
Dim files As String() = New String() {"img2.jpg", "img1.jpg", "img10.jpg"}

'自然順ソートで並び替える
Array.Sort(files, New LogicalStringComparer())

'並び替えた結果を表示する
Console.WriteLine(String.Join(", ", files))
'img1.jpg, img2.jpg, img10.jpg
}}

#code(csharp){{
//並び替える文字列の配列
string[] files = new string[] { "img2.jpg", "img1.jpg", "img10.jpg" };

//自然順ソートで並び替える
Array.Sort(files, new LogicalStringComparer());

//並び替えた結果を表示する
Console.WriteLine(string.Join(", ", files));
//img1.jpg, img2.jpg, img10.jpg
}}

LINQを使って並び替える例は、以下のようになります。

#code(vbnet){{
'並び替える文字列の配列
Dim files As String() = New String() {"img2.jpg", "img1.jpg", "img10.jpg"}

'自然順ソートで並び替えられた配列を取得する
Dim sortedArray As String() = _
    files.OrderBy(Function(f) f, New LogicalStringComparer()).ToArray()
}}

#code(csharp){{
//並び替える文字列の配列
string[] files = new string[] { "img2.jpg", "img1.jpg", "img10.jpg" };

//自然順ソートで並び替えられた配列を取得する
string[] sortedArray =
    files.OrderBy(f => f, new LogicalStringComparer()).ToArray();
}}

このクラスを使って次のような配列を並べ替えた時、

-a 2.txt
-a01.txt
-a02.txt
-a1 0.txt
-a1.txt
-a10.txt
-a100.txt
-a１１.txt
-a2.txt
-a29b.txt
-a2b.txt
-a3.txt

以下のような順番になりました（Windows 8）。

-a 2.txt
-a01.txt
-a1 0.txt
-a1.txt
-a02.txt
-a2.txt
-a2b.txt
-a3.txt
-a10.txt
-a１１.txt
-a29b.txt
-a100.txt

**自分で何とかしてみる [#c0b7a30c]

次に、自分でなんとかする方法を考えてみます。

自然順ソートというものに定義があるのかと思って調べてみたのですが見つからなかったので、自分なりに勝手に考えてみます。

通常の文字列比較は、先頭から1文字ずつ文字を比較していき、違いが見つかったところでその文字の大小を文字列全体の大小とするというようなやり方ではないでしょうか。

これに対して自然順ソートの文字列比較では、文字列内の数字の部分を数値として比較しなければなりません。つまり、文字列の中で数字が連続する部分（以下、数字部分）と、数字以外の文字（以下、非数字）が連続する部分（以下、非数字部分）を分けて、数字部分は数値に変換して数値で比較し、非数字部分は通常の文字列比較と同じように比較します。

他にも、半角数字と全角数字の扱い、スペース文字の扱い、先頭に"0"がある数字の扱いなど、細かい取り決めが必要ですが、それはケースバイケースで考えることにします。

***正規表現を使用して文字列を分割する方法 [#f2b38641]

まずは、文字列を数字部分と非数字部分に分割する方法を考えてみます。

Regex.Splitメソッドを使えば、それが可能です。正規表現パターンに"(\d+)"のようなものを使えば、{（非数字部分）, （数字部分）, （非数字部分）, ...}のように、非数字部分と数字部分が交互に現れる配列として分割した結果を取得できます。

このようにして取得した配列を先頭から順番に比較していき、違いがあればその結果を返し、同じならば次の部分を比較します。この時、非数字部分であれば文字列として比較しますが、数字部分であればこれを数値に変換して比較します。

このような方法で2つの文字列を比較するIComparerの例を以下に示します。

この例では、文字列を分割する正規表現パターンを"\s*([0-9]+)\s*"のようにしました。"[0-9]"としているのは、"\d"を使うと全角数字なども対象になってしまい、数値に変換するのが大変になるからです。"\s*"をつけているのは、数字の前後のスペース文字を無視するためです。（もし無視したくないのであれば、これを削除してください。）

また、"1"と"01"のように、数字が違っても数値が違う場合は、数字部分の長さの比較結果を覚えておいて、もし最後まで違いがなかった時に、その結果を返すようにしています。それも同じだった場合は、文字列の長さを比較しています。

#code(vbnet){{
Imports System.Text.RegularExpressions

''' <summary>
''' 文字列内に含まれている半角数字を考慮して文字列を比較します。
''' </summary>
Public Class NaturalStringComparer
    Implements System.Collections.IComparer
    Implements System.Collections.Generic.IComparer(Of String)

    Private comparisonType As StringComparison

    ''' <summary>
    ''' NaturalStringComparerのコンストラクタ。
    ''' </summary>
    ''' <param name="compType">
    ''' 文字列を比較する方法を表すStringComparison。
    ''' </param>
    Public Sub New(compType As StringComparison)
        Me.comparisonType = compType
    End Sub

    ''' <summary>
    ''' NaturalStringComparerのコンストラクタ。
    ''' </summary>
    Public Sub New()
        Me.New(StringComparison.CurrentCulture)
    End Sub

    Public Function Compare(x As String, y As String) As Integer _
        Implements System.Collections.Generic.IComparer(Of String).Compare

        If x Is Nothing Then
            If y Is Nothing Then
                Return 0
            End If
            Return -1
        End If
        If y Is Nothing Then
            Return 1
        End If

        '数字部分で文字列を分割する
        '数字の前後のスペースは省略する
        Dim splitReg As New Regex("\s*([0-9]+)\s*")
        Dim aryX As String() = splitReg.Split(x)
        Dim aryY As String() = splitReg.Split(y)

        Dim minLen As Integer = Math.Min(aryX.Length, aryY.Length)
        Dim firstComp As Integer = 0

        For i As Integer = 0 To minLen - 1
            '非数字部分を取得
            Dim strX As String = aryX(i)
            Dim strY As String = aryY(i)
            '非数字部分が違う時は、その結果を返す
            Dim strComp As Integer = _
                String.Compare(strX, strY, Me.comparisonType)
            If strComp <> 0 Then
                Return strComp
            End If

            '数字部分を取得
            i += 1
            If minLen <= i Then
                Exit For
            End If
            strX = aryX(i)
            strY = aryY(i)
            '数字を数値に変換
            Dim numX As Double
            Dim numY As Double
            If Double.TryParse(strX, numX) AndAlso _
                Double.TryParse(strY, numY) Then
                '数値が違う時は、その結果を返す
                If numX <> numY Then
                    Return numX.CompareTo(numY)
                End If
                '同じ数値の場合は、どちらの文字列が長いか覚えておく
                If firstComp = 0 Then
                    firstComp = strX.Length - strY.Length
                End If
            Else
                '数値に変換できなかった時は、文字列として比較する
                Return String.Compare(strX, strY, Me.comparisonType)
            End If
        Next

        'すべての部分が同じと判断された時
        '数字部分の文字列に違いがあった時は、その結果を返す
        If firstComp <> 0 Then
            Return firstComp
        End If

        '最後まで同じだった時は、文字列の長さを比較する
        Return x.Length - y.Length
    End Function

    Public Function Compare(x As Object, y As Object) As Integer _
        Implements System.Collections.IComparer.Compare
        Return Me.Compare(x.ToString(), y.ToString())
    End Function
End Class
}}

#code(csharp){{
using System;
using System.Text.RegularExpressions;

/// <summary>
/// 文字列内に含まれている半角数字を考慮して文字列を比較します。
/// </summary>
public class NaturalStringComparer :
    System.Collections.IComparer,
    System.Collections.Generic.IComparer<string>
{
    private StringComparison comparisonType;

    /// <summary>
    /// NaturalStringComparerのコンストラクタ。
    /// </summary>
    /// <param name="compType">
    /// 文字列を比較する方法を表すStringComparison。
    /// </param>
    public NaturalStringComparer(StringComparison compType)
    {
        this.comparisonType = compType;
    }
    /// <summary>
    /// NaturalStringComparerのコンストラクタ。
    /// </summary>
    public NaturalStringComparer()
        : this(StringComparison.CurrentCulture)
    {
    }

    public int Compare(string x, string y)
    {
        if (x == null)
        {
            if (y == null)
            {
                return 0;
            }
            return -1;
        }
        if (y == null)
        {
            return 1;
        }

        //数字部分で文字列を分割する
        //数字の前後のスペースは省略する
        Regex splitReg = new Regex(@"\s*([0-9]+)\s*");
        string[] aryX = splitReg.Split(x);
        string[] aryY = splitReg.Split(y);

        int minLen = Math.Min(aryX.Length, aryY.Length);
        int firstComp = 0;

        for (int i = 0; i < minLen; i++)
        {
            //非数字部分を取得
            string strX = aryX[i];
            string strY = aryY[i];
            //非数字部分が違う時は、その結果を返す
            int strComp = string.Compare(strX, strY, this.comparisonType);
            if (strComp != 0)
            {
                return strComp;
            }

            //数字部分を取得
            i++;
            if (minLen <= i)
            {
                break;
            }
            strX = aryX[i];
            strY = aryY[i];
            //数字を数値に変換
            double numX;
            double numY;
            if (double.TryParse(strX, out numX) &&
                double.TryParse(strY, out numY))
            {
                //数値が違う時は、その結果を返す
                if (numX != numY)
                {
                    return numX.CompareTo(numY);
                }
                //同じ数値の場合は、どちらの文字列が長いか覚えておく
                if (firstComp == 0)
                {
                    firstComp = strX.Length - strY.Length;
                }
            }
            else
            {
                //数値に変換できなかった時は、文字列として比較する
                return string.Compare(strX, strY, this.comparisonType);
            }
        }

        //すべての部分が同じと判断された時
        //数字部分の文字列に違いがあった時は、その結果を返す
        if (firstComp != 0)
        {
            return firstComp;
        }

        //最後まで同じだった時は、文字列の長さを比較する
        return x.Length - y.Length;
    }

    public int Compare(object x, object y)
    {
        return this.Compare(x.ToString(), y.ToString());
    }
}
}}

このクラスを使って次の配列を並び替えると、

-a 2.txt
-a01.txt
-a02.txt
-a1 0.txt
-a1.txt
-a10.txt
-a100.txt
-a１１.txt
-a2.txt
-a29b.txt
-a2b.txt
-a3.txt

以下のような順番になりました。

-a1 0.txt
-a1.txt
-a01.txt
-a2.txt
-a 2.txt
-a02.txt
-a2b.txt
-a3.txt
-a10.txt
-a29b.txt
-a100.txt
-a１１.txt

この方法は正規表現を使用しているため、きっと遅いです。「[[Natural Sort Comparer - CodeProject>http://www.codeproject.com/Articles/22517/Natural-Sort-Comparer]]」で紹介されている方法はこれとほぼ同じやり方みたいですが、文字列を分割した結果をDictionaryのテーブルとして保存しているため、その点改善されています。

***先頭から1文字ずつ比較していく方法 [#q2b3a692]

もっと単純に、文字列の先頭から1文字ずつ比較していく方法を考えてみます。

1文字ずつ比較していき、違いが見つかったとします。もし違いのあった文字が両方とも非数字だったら、普通に文字の比較結果を返します。両方とも数字だったら、その数字が含まれている数字部分を数値に変換して、数値としての比較結果を返します。片方だけが数字だった場合は、その前の文字が数字であるかを調べ、数字であればその数字部分を数値に変換して比較し、数字でなければ単純に文字を比較した結果を返します。

このようにして文字列を比較するIComparerの例を以下に示します。この例では、半角数字と全角数字を区別せずに、どちらも同じ数値になるようにしています。全角数字を非数字として扱うならば、もっと簡単にできると思います。

#code(vbnet){{
''' <summary>
''' 文字列内に含まれている半角、全角数字を考慮して文字列を比較します。
''' </summary>
Public Class StringNaturalComparer
    Implements System.Collections.IComparer
    Implements System.Collections.Generic.IComparer(Of String)

    Public Function Compare(x As String, y As String) As Integer _
        Implements System.Collections.Generic.IComparer(Of String).Compare

        If x Is Nothing Then
            If y Is Nothing Then
                Return 0
            End If
            Return -1
        End If
        If y Is Nothing Then
            Return 1
        End If

        Dim xLen As Integer = x.Length
        Dim yLen As Integer = y.Length
        Dim xIndex As Integer = 0
        Dim yIndex As Integer = 0
        Dim firstResult As Integer = 0

        '１文字ずつ調べる
        While (xIndex < xLen) AndAlso (yIndex < yLen)
            Dim xChar As Char = x(xIndex)
            Dim yChar As Char = y(yIndex)

            If xChar <> yChar Then
                '違う文字が見つかった時
                'その文字が数字か調べる
                Dim xDigit As Boolean = IsDigit(xChar)
                Dim yDigit As Boolean = IsDigit(yChar)

                '片方だけが数字で、一つ前の文字が数字の時
                If xDigit AndAlso Not yDigit AndAlso _
                    (0 < yIndex) AndAlso IsDigit(y(yIndex - 1)) Then
                    '非数字の方を一つ前に戻す
                    yIndex -= 1
                    yChar = y(yIndex)
                    yDigit = True
                ElseIf Not xDigit AndAlso yDigit AndAlso _
                    (0 < xIndex) AndAlso IsDigit(x(xIndex - 1)) Then
                    xIndex -= 1
                    xChar = x(xIndex)
                    xDigit = True
                End If

                If xDigit AndAlso yDigit Then
                    '両方とも数字の時
                    '数字部分を数値に変換して比較する
                    Dim xNum As Double = ConvertStringToNumber(x, xIndex)
                    Dim yNum As Double = ConvertStringToNumber(y, yIndex)
                    '数値が違ったら、その結果を返す
                    If xNum <> yNum Then
                        Return xNum.CompareTo(yNum)
                    End If
                    '数値が同じだったら、文字を比較した結果を覚えておく
                    If firstResult = 0 Then
                        firstResult = xChar.CompareTo(yChar)
                    End If
                Else
                    '両方とも非数字か、片方が数字で前の文字が非数字の時
                    '文字を比較した結果を返す
                    Return xChar.CompareTo(yChar)
                End If
            End If

            '次の文字へ
            xIndex += 1
            yIndex += 1
        End While

        '最後まで違いがなかった時
        '数字部分に違いがあったら、その結果を返す
        If firstResult <> 0 Then
            Return firstResult
        End If

        '最後は文字列の長さを比較する
        Return xLen - yLen
    End Function

    Public Function Compare(x As Object, y As Object) As Integer _
        Implements System.Collections.IComparer.Compare
        Return Me.Compare(x.ToString(), y.ToString())
    End Function

    ''' <summary>
    ''' 指定されたインデックスの前後で数字が連続する部分を数値に変換
    ''' </summary>
    ''' <param name="s">対象とする文字列</param>
    ''' <param name="index">変換する数字部分のインデックス。
    ''' 呼び出し後は数字部分の最後のインデックスが格納される。</param>
    ''' <returns>該当する数字部分が変換された数値。</returns>
    Private Shared Function ConvertStringToNumber( _
        s As String, ByRef index As Integer) As Double

        Dim sum As Double = 0.0

        'indexの前の数字部分を数値に変換
        Dim e As Double = 1.0
        Dim i As Integer = index - 1
        While 0 <= i
            '数字の文字を数値に変換して、前に結果に加算
            Dim num As Integer = ConvertCharToInt32(s(i))
            If num < 0 Then
                Exit While
            End If
            sum += num * e
            e *= 10.0
            i -= 1
        End While

        'indexから後の数字部分を数値に変換
        While index < s.Length
            Dim num As Integer = ConvertCharToInt32(s(index))
            If num < 0 Then
                Exit While
            End If
            sum = sum * 10.0 + num
            index += 1
        End While

        index -= 1
        Return sum
    End Function

    ''' <summary>
    ''' 数字を数値に変換する
    ''' </summary>
    ''' <param name="c">変換する文字</param>
    ''' <returns>半角、全角数字の時は、数値。それ以外は-1。</returns>
    Private Shared Function ConvertCharToInt32(c As Char) As Integer
        If "0"c <= c AndAlso c <= "9"c Then
            Return AscW(c) - AscW("0"c)
        ElseIf "０"c <= c AndAlso c <= "９"c Then
            Return AscW(c) - AscW("０"c)
        End If
        Return -1
    End Function

    ''' <summary>
    ''' 文字が数字が調べる
    ''' </summary>
    ''' <param name="c">調べる文字</param>
    ''' <returns>文字が半角、全角数字ならTrue。それ以外はFalse。</returns>
    Private Shared Function IsDigit(c As Char) As Boolean
        Return ("0"c <= c AndAlso c <= "9"c) OrElse _
            ("０"c <= c AndAlso c <= "９"c)
    End Function
End Class
}}

#code(csharp){{
using System;

/// <summary>
/// 文字列内に含まれている半角、全角数字を考慮して文字列を比較します。
/// </summary>
public class StringNaturalComparer :
    System.Collections.IComparer,
    System.Collections.Generic.IComparer<string>
{
    public int Compare(string x, string y)
    {
        if (x == null)
        {
            if (y == null)
            {
                return 0;
            }
            return -1;
        }
        if (y == null)
        {
            return 1;
        }

        int xLen = x.Length;
        int yLen = y.Length;
        int xIndex = 0;
        int yIndex = 0;
        int firstResult = 0;

        //１文字ずつ調べる
        while ((xIndex < xLen) && (yIndex < yLen))
        {
            char xChar = x[xIndex];
            char yChar = y[yIndex];

            if (xChar != yChar)
            {
                //違う文字が見つかった時
                //その文字が数字か調べる
                bool xDigit = IsDigit(xChar);
                bool yDigit = IsDigit(yChar);

                //片方だけが数字で、一つ前の文字が数字の時
                if (xDigit && !yDigit &&
                    (0 < yIndex) && IsDigit(y[yIndex - 1]))
                {
                    //非数字の方を一つ前に戻す
                    yIndex--;
                    yChar = y[yIndex];
                    yDigit = true;
                }
                else if (!xDigit && yDigit &&
                    (0 < xIndex) && IsDigit(x[xIndex - 1]))
                {
                    xIndex--;
                    xChar = x[xIndex];
                    xDigit = true;
                }

                if (xDigit && yDigit)
                {
                    //両方とも数字の時
                    //数字部分を数値に変換して比較する
                    double xNum = ConvertStringToNumber(x, ref xIndex);
                    double yNum = ConvertStringToNumber(y, ref yIndex);
                    //数値が違ったら、その結果を返す
                    if (xNum != yNum)
                    {
                        return xNum.CompareTo(yNum);
                    }
                    //数値が同じだったら、文字を比較した結果を覚えておく
                    if (firstResult == 0)
                    {
                        firstResult = xChar.CompareTo(yChar);
                    }
                }
                else
                {
                    //両方とも非数字か、片方が数字で前の文字が非数字の時
                    //文字を比較した結果を返す
                    return xChar.CompareTo(yChar);
                }
            }

            //次の文字へ
            xIndex++;
            yIndex++;
        }

        //最後まで違いがなかった時
        //数字部分に違いがあったら、その結果を返す
        if (firstResult != 0)
        {
            return firstResult;
        }

        //最後は文字列の長さを比較する
        return xLen - yLen;
    }

    public int Compare(object x, object y)
    {
        return this.Compare(x.ToString(), y.ToString());
    }

    /// <summary>
    /// 指定されたインデックスの前後で数字が連続する部分を数値に変換
    /// </summary>
    /// <param name="s">対象とする文字列</param>
    /// <param name="index">変換する数字部分のインデックス。
    /// 呼び出し後は数字部分の最後のインデックスが格納される。</param>
    /// <returns>該当する数字部分が変換された数値。</returns>
    private static double ConvertStringToNumber(string s, ref int index)
    {
        double sum = 0.0;

        //indexの前の数字部分を数値に変換
        double e = 1.0;
        for (int i = index - 1; 0 <= i; i--)
        {
            //数字の文字を数値に変換して、前に結果に加算
            int num = ConvertCharToInt32(s[i]);
            if (num < 0)
            {
                break;
            }
            sum += num * e;
            e *= 10.0;
        }

        //indexから後の数字部分を数値に変換
        for (; index < s.Length; index++)
        {
            int num = ConvertCharToInt32(s[index]);
            if (num < 0)
            {
                break;
            }
            sum = sum * 10.0 + num;
        }

        index--;
        return sum;
    }

    /// <summary>
    /// 数字を数値に変換する
    /// </summary>
    /// <param name="c">変換する文字</param>
    /// <returns>半角、全角数字の時は、数値。それ以外は-1。</returns>
    private static int ConvertCharToInt32(char c)
    {
        if ('0' <= c && c <= '9')
        {
            return (int)c - (int)'0';
        }
        else if ('０' <= c && c <= '９')
        {
            return (int)c - (int)'０';
        }
        return -1;
    }

    /// <summary>
    /// 文字が数字が調べる
    /// </summary>
    /// <param name="c">調べる文字</param>
    /// <returns>文字が半角、全角数字ならTrue。それ以外はFalse。</returns>
    private static bool IsDigit(char c)
    {
        return ('0' <= c && c <= '9') || ('０' <= c && c <= '９');
    }
}
}}

このクラスを使って次の配列を並べ替えると、

-a 2.txt
-a01.txt
-a02.txt
-a1 0.txt
-a1.txt
-a10.txt
-a100.txt
-a１１.txt
-a2.txt
-a29b.txt
-a2b.txt
-a3.txt

以下のような順番になりました。

-a 2.txt
-a1 0.txt
-a01.txt
-a1.txt
-a02.txt
-a2.txt
-a2b.txt
-a3.txt
-a10.txt
-a１１.txt
-a29b.txt
-a100.txt

**Natural Order String Comparison を参考にする [#hb1d0214]

「[[Natural Order String Comparison>http://sourcefrog.net/projects/natsort/]]」に、Martin Poolさんが作成した自然順文字列比較を行うC言語のコードがあります。これは、PHPの[[strnatcmp>http://php.net/manual/ja/function.strnatcmp.php]]や[[strnatcasecmp>http://php.net/manual/ja/function.strnatcasecmp.php]]関数の基になっているそうです。

これをC#とVB.NETで書いてみたものを以下に紹介します。

#code(vbnet){{
'strnatcmp.vb
'Copyright (C) 2013 by DOBON! <http://dobon.net>
'Copyright (C) 2013 by DOBON! <https://dobon.net>
'
'Based on
'strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
'Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net>
'
'This software is provided 'as-is', without any express or implied
'warranty.  In no event will the authors be held liable for any damages
'arising from the use of this software.
'
'Permission is granted to anyone to use this software for any purpose,
'including commercial applications, and to alter it and redistribute it
'freely, subject to the following restrictions:
'
'1. The origin of this software must not be misrepresented; you must not
'   claim that you wrote the original software. If you use this software
'   in a product, an acknowledgment in the product documentation would be
'   appreciated but is not required.
'2. Altered source versions must be plainly marked as such, and must not be
'   misrepresented as being the original software.
'3. This notice may not be removed or altered from any source distribution.

''' <summary>
''' 自然順アルゴリズムにより文字列比較を行います。
''' </summary>
Public Class StrNatComparer
    Implements System.Collections.IComparer
    Implements System.Collections.Generic.IComparer(Of String)

    Private ignoreCase As Boolean = False

    ''' <summary>
    ''' StrNatComparerのコンストラクタ。
    ''' </summary>
    ''' <param name="ignoreCaseComparer">
    ''' 大文字小文字を区別しない文字列比較を行います
    ''' </param>
    Public Sub New(ignoreCaseComparer As Boolean)
        Me.ignoreCase = ignoreCaseComparer
    End Sub

    Public Sub New()
        Me.New(False)
    End Sub

    Public Function Compare(a As String, b As String) As Integer _
        Implements System.Collections.Generic.IComparer(Of String).Compare
        Return StrNatCmp0(a, b, Me.ignoreCase)
    End Function

    Public Function Compare(a As Object, b As Object) As Integer _
        Implements System.Collections.IComparer.Compare
        Return Me.Compare(a.ToString(), b.ToString())
    End Function

    ''' <summary>
    ''' 指定した文字列内の指定したインデックスの文字を返します。
    ''' </summary>
    ''' <param name="s">対象とする文字列。</param>
    ''' <param name="index">取得したい文字があるインデックス。</param>
    ''' <returns>指定したインデックスに文字があれば、その文字。
    ''' なければ、'\0'。</returns>
    Private Shared Function GetChar(s As String, index As Integer) As Char
        If (index < 0) OrElse (s.Length <= index) Then
            Return ControlChars.NullChar
        End If
        Return s(index)
    End Function

    ' These are defined as macros to make it easier to adapt this code to
    ' different characters types or comparison functions. 
    Private Shared Function IsDigit(c As Char) As Boolean
        Return ("0"c <= c) AndAlso (c <= "9"c)
    End Function

    Private Shared Function IsSpace(c As Char) As Boolean
        Return Char.IsWhiteSpace(c)
    End Function

    Private Shared Function ToUpper(c As Char) As Char
        Return Char.ToUpper(c, _
            System.Globalization.CultureInfo.InvariantCulture)
    End Function

    Private Shared Function CompareRight(a As String, b As String, _
        ai As Integer, bi As Integer) As Integer

        Dim bias As Integer = 0

        ' The longest run of digits wins.  That aside, the greatest
        ' value wins, but we can't know that it will until we've scanned
        ' both numbers to know that they have the same magnitude, so we
        ' remember it in BIAS. 
        While True
            Dim ca As Char = GetChar(a, ai)
            Dim cb As Char = GetChar(b, bi)

            If Not IsDigit(ca) AndAlso Not IsDigit(cb) Then
                Return bias
            ElseIf Not IsDigit(ca) Then
                Return -1
            ElseIf Not IsDigit(cb) Then
                Return 1
            ElseIf ca < cb Then
                If bias <> 0 Then
                    bias = -1
                End If
            ElseIf ca > cb Then
                If bias <> 0 Then
                    bias = 1
                End If
            ElseIf ca = ControlChars.NullChar AndAlso _
                cb = ControlChars.NullChar Then
                Return bias
            End If

            ai += 1
            bi += 1
        End While
    End Function

    Private Shared Function CompareLeft(a As String, b As String, _
        ai As Integer, bi As Integer) As Integer

        ' Compare two left-aligned numbers: the first to have a
        '  different value wins. 
        While True
            Dim ca As Char = GetChar(a, ai)
            Dim cb As Char = GetChar(b, bi)

            If Not IsDigit(ca) AndAlso Not IsDigit(cb) Then
                Return 0
            ElseIf Not IsDigit(ca) Then
                Return -1
            ElseIf Not IsDigit(cb) Then
                Return 1
            ElseIf ca < cb Then
                Return -1
            ElseIf ca > cb Then
                Return 1
            End If

            ai += 1
            bi += 1
        End While
    End Function

    Private Shared Function StrNatCmp0(a As String, b As String, _
        foldCase As Boolean) As Integer

        If a Is Nothing Then
            If b Is Nothing Then
                Return 0
            End If
            Return -1
        End If
        If b Is Nothing Then
            Return 1
        End If

        Dim ai As Integer = 0
        Dim bi As Integer = 0

        While True
            Dim ca As Char = GetChar(a, ai)
            Dim cb As Char = GetChar(b, bi)

            ' skip over leading spaces or zeros 
            While Char.IsWhiteSpace(ca)
                ai += 1
                ca = GetChar(a, ai)
            End While

            While Char.IsWhiteSpace(cb)
                bi += 1
                cb = GetChar(b, bi)
            End While

            ' process run of digits 
            If IsDigit(ca) AndAlso IsDigit(cb) Then
                Dim fractional As Boolean = (ca = "0"c OrElse cb = "0"c)
                If fractional Then
                    Dim result As Integer = CompareLeft(a, b, ai, bi)
                    If result <> 0 Then
                        Return result
                    End If
                Else
                    Dim result As Integer = CompareRight(a, b, ai, bi)
                    If result <> 0 Then
                        Return result
                    End If
                End If
            End If

            If ca = ControlChars.NullChar AndAlso _
                cb = ControlChars.NullChar Then
                ' The strings compare the same.  Perhaps the caller
                '     will want to call strcmp to break the tie. 
                Return 0
            End If

            If foldCase Then
                ca = Char.ToUpper(ca)
                cb = Char.ToUpper(cb)
            End If

            If ca < cb Then
                Return -1
            ElseIf ca > cb Then
                Return 1
            End If

            ai += 1
            bi += 1
        End While
    End Function

    Public Function StrNatCmp(a As String, b As String) As Integer
        Return StrNatCmp0(a, b, False)
    End Function

    ' Compare, recognizing numeric string and ignoring case. 
    Public Function StrNatCaseCmp(a As String, b As String) As Integer
        Return StrNatCmp0(a, b, True)
    End Function
End Class
}}

#code(csharp){{
using System;

/*
strnatcmp.cs
Copyright (C) 2013 by DOBON! <http://dobon.net>
Copyright (C) 2013 by DOBON! <https://dobon.net>

Based on
strnatcmp.c -- Perform 'natural order' comparisons of strings in C.
Copyright (C) 2000, 2004 by Martin Pool <mbp sourcefrog net>

This software is provided 'as-is', without any express or implied
warranty.  In no event will the authors be held liable for any damages
arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not
   claim that you wrote the original software. If you use this software
   in a product, an acknowledgment in the product documentation would be
   appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
   misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
*/

/// <summary>
/// 自然順アルゴリズムにより文字列比較を行います。
/// </summary>
public class StrNatComparer :
    System.Collections.IComparer,
    System.Collections.Generic.IComparer<string>
{
    private bool ignoreCase = false;

    /// <summary>
    /// StrNatComparerのコンストラクタ。
    /// </summary>
    /// <param name="ignoreCaseComparer">
    /// 大文字小文字を区別しない文字列比較を行います
    /// </param>
    public StrNatComparer(bool ignoreCaseComparer)
    {
        this.ignoreCase = ignoreCaseComparer;
    }
    public StrNatComparer()
        : this(false)
    {
    }

    public int Compare(string a, string b)
    {
        return StrNatCmp0(a, b, this.ignoreCase);
    }

    public int Compare(object a, object b)
    {
        return this.Compare(a.ToString(), b.ToString());
    }

    /// <summary>
    /// 指定した文字列内の指定したインデックスの文字を返します。
    /// </summary>
    /// <param name="s">対象とする文字列。</param>
    /// <param name="index">取得したい文字があるインデックス。</param>
    /// <returns>指定したインデックスに文字があれば、その文字。
    /// なければ、'\0'。</returns>
    private static char GetChar(string s, int index)
    {
        if ((index < 0) || (s.Length <= index))
        {
            return '\0';
        }
        return s[index];
    }

    /* These are defined as macros to make it easier to adapt this code to
       different characters types or comparison functions. */
    private static bool IsDigit(char c)
    {
        return ('0' <= c) && (c <= '9');
    }

    private static bool IsSpace(char c)
    {
        return char.IsWhiteSpace(c);
    }

    private static char ToUpper(char c)
    {
        return char.ToUpper(c,
            System.Globalization.CultureInfo.InvariantCulture);
    }

    private static int CompareRight(string a, string b, int ai, int bi)
    {
        int bias = 0;

        /* The longest run of digits wins.  That aside, the greatest
        value wins, but we can't know that it will until we've scanned
        both numbers to know that they have the same magnitude, so we
        remember it in BIAS. */
        for (; ; ai++, bi++)
        {
            char ca = GetChar(a, ai);
            char cb = GetChar(b, bi);

            if (!IsDigit(ca) && !IsDigit(cb))
            {
                return bias;
            }
            else if (!IsDigit(ca))
            {
                return -1;
            }
            else if (!IsDigit(cb))
            {
                return 1;
            }
            else if (ca < cb)
            {
                if (bias != 0)
                {
                    bias = -1;
                }
            }
            else if (ca > cb)
            {
                if (bias != 0)
                {
                    bias = 1;
                }
            }
            else if (ca == '\0' && cb == '\0')
            {
                return bias;
            }
        }
    }

    private static int CompareLeft(string a, string b, int ai, int bi)
    {
        /* Compare two left-aligned numbers: the first to have a
           different value wins. */
        for (; ; ai++, bi++)
        {
            char ca = GetChar(a, ai);
            char cb = GetChar(b, bi);

            if (!IsDigit(ca) && !IsDigit(cb))
            {
                return 0;
            }
            else if (!IsDigit(ca))
            {
                return -1;
            }
            else if (!IsDigit(cb))
            {
                return 1;
            }
            else if (ca < cb)
            {
                return -1;
            }
            else if (ca > cb)
            {
                return 1;
            }
        }
    }

    private static int StrNatCmp0(string a, string b, bool foldCase)
    {
        if (a == null)
        {
            if (b == null)
            {
                return 0;
            }
            return -1;
        }
        if (b == null)
        {
            return 1;
        }

        int ai = 0;
        int bi = 0;

        while (true)
        {
            char ca = GetChar(a, ai);
            char cb = GetChar(b, bi);

            /* skip over leading spaces or zeros */
            while (char.IsWhiteSpace(ca))
            {
                ai++;
                ca = GetChar(a, ai);
            }

            while (char.IsWhiteSpace(cb))
            {
                bi++;
                cb = GetChar(b, bi);
            }

            /* process run of digits */
            if (IsDigit(ca) && IsDigit(cb))
            {
                bool fractional = (ca == '0' || cb == '0');
                if (fractional)
                {
                    int result = CompareLeft(a, b, ai, bi);
                    if (result != 0)
                    {
                        return result;
                    }
                }
                else
                {
                    int result = CompareRight(a, b, ai, bi);
                    if (result != 0)
                    {
                        return result;
                    }
                }
            }

            if (ca == '\0' && cb == '\0')
            {
                /* The strings compare the same.  Perhaps the caller
                       will want to call strcmp to break the tie. */
                return 0;
            }

            if (foldCase)
            {
                ca = char.ToUpper(ca);
                cb = char.ToUpper(cb);
            }

            if (ca < cb)
            {
                return -1;
            }
            else if (ca > cb)
            {
                return 1;
            }

            ai++;
            bi++;
        }
    }

    public int StrNatCmp(string a, string b)
    {
        return StrNatCmp0(a, b, false);
    }

    /* Compare, recognizing numeric string and ignoring case. */
    public int StrNatCaseCmp(string a, string b)
    {
        return StrNatCmp0(a, b, true);
    }
}
}}

このクラスを使って次の配列を並べ替えると、

-a 2.txt
-a01.txt
-a02.txt
-a1 0.txt
-a1.txt
-a10.txt
-a100.txt
-a１１.txt
-a2.txt
-a29b.txt
-a2b.txt
-a3.txt

以下のような順番になりました。

-a01.txt
-a02.txt
-a1.txt
-a1 0.txt
-a2.txt
-a 2.txt
-a2b.txt
-a3.txt
-a10.txt
-a29b.txt
-a100.txt
-a１１.txt

**その他の参考になるページ [#f04d39d0]

最後に、上記で紹介した以外の、参考になりそうなページを紹介します。

-[[The Alphanum Algorithm>http://www.davekoelle.com/alphanum.html]]
-[[Natural Sorting in C#>http://www.interact-sw.co.uk/iangblog/2007/12/13/natural-sorting]]
-[[Numeric String Sort in C# - CodeProject>http://www.codeproject.com/Articles/11016/Numeric-String-Sort-in-C]]
-[[Implementing the .NET IComparer interface to get a more natural sort order - CodeProject>http://www.codeproject.com/Articles/22978/Implementing-the-NET-IComparer-interface-to-get-a]]
-[[tgmayfield: String natural sorting>http://tgmayfield.livejournal.com/396.html?nojs=1]]

**コメント [#b9f9d7ae]
#comment

//これより下は編集しないでください
#pageinfo([[:Category/.NET]] [[:Category/ASP.NET]],2013-10-30 (水) 02:12:12,DOBON!,2013-10-30 (水) 02:12:12,DOBON!)
▲ ▼
DoboWiki
