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

例えば、文字列の配列

  • img2.jpg
  • img1.jpg
  • img10.jpg

があった時、これを通常の方法（「配列やコレクション内の要素を並び替える」で紹介しているような方法）で並び替えると、

  • img1.jpg
  • img10.jpg
  • img2.jpg

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

  • img1.jpg
  • img2.jpg
  • img10.jpg

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

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

なお配列を並び替える方法についてはほとんど説明しませんので、分からない場合は、まず「配列やコレクション内の要素を並び替える」をご覧ください。

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

▲ ▼

StrCmpLogicalWを使用する方法 †

StrCmpLogicalW functionを使うと、エクスプローラと同じ並び順の並び替えができるようになるようです。

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

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

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24

''' <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
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25

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());
    }
}

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

  1
  2
  3
  4
  5
  6
  7
  8
  9

'並び替える文字列の配列
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

  1
  2
  3
  4
  5
  6
  7
  8
  9

//並び替える文字列の配列
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を使って並び替える例は、以下のようになります。

  1
  2
  3
  4
  5
  6

'並び替える文字列の配列
Dim files As String() = New String() {"img2.jpg", "img1.jpg", "img10.jpg"}
 
'自然順ソートで並び替えられた配列を取得する
Dim sortedArray As String() = _
    files.OrderBy(Function(f) f, New LogicalStringComparer()).ToArray()
  1
  2
  3
  4
  5
  6

//並び替える文字列の配列
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
▲ ▼

自分で何とかしてみる †

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

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

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

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

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

▲ ▼

正規表現を使用して文字列を分割する方法 †

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

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

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

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

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

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

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
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

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」で紹介されている方法はこれとほぼ同じやり方みたいですが、文字列を分割した結果をDictionaryのテーブルとして保存しているため、その点改善されています。

▲ ▼

先頭から1文字ずつ比較していく方法 †

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

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

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

''' <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
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

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 を参考にする †

「Natural Order String Comparison」に、Martin Poolさんが作成した自然順文字列比較を行うC言語のコードがあります。これは、PHPのstrnatcmpやstrnatcasecmp関数の基になっているそうです。

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

'strnatcmp.vb
'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
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269

using System;
 
/*
strnatcmp.cs
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
▲ ▼

その他の参考になるページ †

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

▲ ▼

コメント †

  • 先頭から1文字ずつ比較していく方法（VB.NET）だけど、68行目を「Return String.Compare(xChar, yChar, True)」にした方が自然かも。 -- Jane Doe 2017-02-25 (土) 17:38:02

▲ ▼
ページ情報
[ トップ ]   [ 編集 | 凍結 | 差分 | バックアップ | 添付 | 複製 | 名前変更 | リロード ]   [ 新規 | 子ページ作成 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]