ここでは複合型を含むコレクションのソートについて見ていきます。
複合型のソート
数値や文字列などの型は、あらかじめデフォルトの並べ替え順序が定義されているため特に何も指定しなくてもArray.SortやList.Sortなどのメソッドでソートを行うことが出来ます。 一方、独自に定義したクラス・構造体などの複合型(1つ以上の基本型を組み合わせて構成される型)の場合は、並べ替え順序を個別に定義しない限りソートすることが出来ません。
仮に型が比較演算子をオーバーロードしていてもそれだけではソート出来るようにはなりません。 この点については、比較演算子のオーバーロードとIComparable<T>インターフェイスで詳しく解説しています。
ここでは、複合型をソートする方法・並べ替え順序を定義する方法について解説します。
Sort + Comparison<T>
降順でのソートでも述べているとおり、Array.SortメソッドおよびList.Sortメソッドでは、並び替え順序を定義したメソッドを用意し、それをComparison<T>デリゲートとしてSortメソッドの引数に指定することにより、デフォルト(昇順)以外の順序、独自に定義した順序でソートすることが出来ます。
早速、独自に定義したクラスをソートする方法、並べ替え順序を定義する方法について順を追って見ていきます。
ここではNameフィールド(string)とIDフィールド(int)を持つクラスAccountを作成し、Accountクラスのインスタンスが格納されたリストをID順にソートすることにします。 具体的には、次の不完全なコードでソートが出来るように実装していきます。
以下のコードで複合型のコレクションをソートできるようにしたい
using System;
using System.Collections.Generic;
class Account {
public int ID;
public string Name;
public Account(int id, string name)
{
this.ID = id;
this.Name = name;
}
}
class Sample {
static void Main()
{
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob"),
new Account(1, "Dave"),
new Account(2, "Alice"),
new Account(5, "Charlie"),
new Account(4, "Eve"),
});
// このままではソート出来ない (InvalidOperationExceptionがスローされる)
// list.Sort();
foreach (Account a in list) {
Console.WriteLine("{0} {1}", a.ID, a.Name);
}
}
}
以下のコードで複合型のコレクションをソートできるようにしたい
Imports System
Imports System.Collections.Generic
Class Account
Public ID As Integer
Public Name As String
Public Sub New(ByVal id As Integer, ByVal name As String)
MyClass.ID = id
MyClass.Name = name
End Sub
End Class
Class Sample
Shared Sub Main()
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob"), _
New Account(1, "Dave"), _
New Account(2, "Alice"), _
New Account(5, "Charlie"), _
New Account(4, "Eve") _
})
' このままではソート出来ない (InvalidOperationExceptionがスローされる)
' list.Sort()
For Each a As Account In list
Console.WriteLine("{0} {1}", a.ID, a.Name)
Next
End Sub
End Class
まずは、並べ替え順序を定義をするために、比較を行うメソッドを用意します。 このメソッドは、Comparison<T>デリゲートの形でSortメソッドに渡す必要があります。 Comparison<T>デリゲートの形式を見てみると、次のようになっています。
Comparison<T>デリゲートのシグネチャ
public delegate int Comparison<in T>(T x, T y);
Comparison<T>デリゲートのシグネチャ
Public Delegate Function Comparison(Of In T)(x As T, y As T) As Integer
この形式を分かりやすく説明すると、「ある型Tの要素二つを比べて、どちらが小さいか・大きいかをintの数値で返す」というものです。 Sortメソッドの内部では、各要素の比較が行われる度にこのメソッドが呼び出され、戻り値として返される大小関係によって要素の並べ替えが行われることになります。 この形式にあわせて、Accountクラスを比較するメソッドCompareAccountのひな形を作成すると次のようになります。
Accountクラスの比較を行うメソッドのひな形
static int CompareAccount(Account x, Account y)
{
return 0; // xとyを比較した結果を返す
}
Accountクラスの比較を行うメソッドのひな形
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
Return 0 ' xとyを比較した結果を返す
End Function
次にこのメソッドを実装します。 比較を行うメソッドでは二つの要素の大小関係を戻り値として返します。 具体的には、引数として渡される二つの要素xとyについて、その大小関係が
- x > y (xがyより大きい) ならば 正の数
- x < y (xがyより小さい) ならば 負の数
- x = y (xとyが等しい) ならば 0
を返すようにします。 このルールに従ってメソッドを実装すると、次のようになります。 正の数・負の数ならなんでもよいので、ここではそれぞれ1と-1を返しています。
大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッドのひな形
static int CompareAccount(Account x, Account y)
{
if (x > y)
return 1; // xがyより大きい
else if (x < y)
return -1; // xがyより小さい
else // if (x == y)
return 0; // xとyが等しい
}
大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッドのひな形
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
If x > y Then
Return 1 ' xがyより大きい
Else If x < y
Return -1 ' xがyより小さい
Else ' If x = y
Return 0 ' xとyが等しい
End If
End Function
当然Accountクラスのインスタンスそのものを比較することはできないため、このままでは不十分です。 ここではID順でのソートを行いたいため、インスタンスの大小関係がIDフィールドの値によって定まるように実装します。 最終的に、ID順でソートするためのメソッドCompareAccountは次のようになります。
IDフィールドの値に従って大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッド
static int CompareAccount(Account x, Account y)
{
if (x.ID > y.ID)
return 1; // xのIDがyのIDより大きい→xはyより大きい
else if (x.ID < y.ID)
return -1; // xのIDがyのIDより小さい→xはyより小さい
else // if (x.ID == y.ID)
return 0; // xのIDとyのIDが等しい→xはyと等しい
}
IDフィールドの値に従って大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッド
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
If x.ID > y.ID Then
Return 1 ' xのIDがyのIDより大きい→xはyより大きい
Else If x.ID < y.ID
Return -1 ' xのIDがyのIDより小さい→xはyより小さい
Else ' If x.ID = y.ID
Return 0 ' xのIDとyのIDが等しい→xはyと等しい
End If
End Function
最後に、このメソッドをSortメソッドの引数として渡せば、リストはこのメソッドで定義された順序、すなわちID順にソートされるようになります。
Accountクラスの比較を行うメソッドを追加してAccountのリストをソートできるようにしたコード
using System;
using System.Collections.Generic;
class Account {
public int ID;
public string Name;
public Account(int id, string name)
{
this.ID = id;
this.Name = name;
}
}
class Sample {
// IDプロパティの値にしたがってAccountクラスの比較を行うメソッド
static int CompareAccount(Account x, Account y)
{
if (x.ID > y.ID)
return 1;
else if (x.ID < y.ID)
return -1;
else // if (x.ID == y.ID)
return 0;
}
static void Main()
{
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob"),
new Account(1, "Dave"),
new Account(2, "Alice"),
new Account(5, "Charlie"),
new Account(4, "Eve"),
});
// 比較用のメソッドを指定してソート
list.Sort(CompareAccount);
foreach (Account a in list) {
Console.WriteLine("{0} {1}", a.ID, a.Name);
}
}
}
Accountクラスの比較を行うメソッドを追加してAccountのリストをソートできるようにしたコード
Imports System
Imports System.Collections.Generic
Class Account
Public ID As Integer
Public Name As String
Public Sub New(ByVal id As Integer, ByVal name As String)
MyClass.ID = id
MyClass.Name = name
End Sub
End Class
Class Sample
' IDプロパティの値にしたがってAccountクラスの比較を行うメソッド
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
If x.ID > y.ID Then
Return 1
Else If x.ID < y.ID
Return -1
Else ' If x.ID = y.ID
Return 0
End If
End Function
Shared Sub Main()
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob"), _
New Account(1, "Dave"), _
New Account(2, "Alice"), _
New Account(5, "Charlie"), _
New Account(4, "Eve") _
})
' 比較用のメソッドを指定してソート
list.Sort(AddressOf CompareAccount)
For Each a As Account In list
Console.WriteLine("{0} {1}", a.ID, a.Name)
Next
End Sub
End Class
実行結果
1 Dave 2 Alice 3 Bob 4 Eve 5 Charlie
名前順にソートしたければ、Nameフィールドの値を比較するようにCompareAccountメソッドの実装を変えるだけで出来ます。 なお、文字列の比較はその都度定義しなくても、既に用意されているString.Compareメソッドを使うことが出来ます。
Nameフィールドの値に従って大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッド
static int CompareAccount(Account x, Account y)
{
// string.Compareメソッドを使って2つのNameフィールドの値の大小関係を取得し、
// それをAccountクラスの大小関係として返す
return string.Compare(x.Name, y.Name);
}
Nameフィールドの値に従って大小関係を表す値を返すようにしたAccountクラスの比較を行うメソッド
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
' String.Compareメソッドを使って2つのNameフィールドの値の大小関係を取得し、
' それをAccountクラスの大小関係として返す
Return String.Compare(x.Name, y.Name)
End Function
実行結果
2 Alice 3 Bob 5 Charlie 1 Dave 4 Eve
このように、並べ替え順序(大小関係)を定義することができ、Comparison<T>デリゲートの形式でSortメソッドに渡すことができれば、どのような複合型でもソートを行うことが出来るようになります。
なお、ここまでは昇順となるようにしてきましたが、降順にしたければCompareAccountで定義する大小関係を逆にするか、Reverseメソッドを使ってソートした後で逆順にするだけです。
降順でのソートについては基本型のソートと昇順・降順でのソート §.降順でのソートを参照してください。
文字列の比較やString.Compareメソッドの詳細に関しては文字列の探索・比較 §.文字列の比較・等価性の検証を参照してください。
null/Nothingの考慮
ソートしたい対象が参照型のコレクションで、かつコレクションにnull/Nothingが含まれる可能性がある場合は、比較を行うメソッドにおいてもnull/Nothingだった場合の考慮を行う必要があります。 具体的には次のようにnull/Nothingとの比較を行うコードを追加します。
引数にnullが渡される可能性のある比較メソッドの実装例
static int CompareAccount(Account x, Account y)
{
if (x == y)
return 0; // 同一のインスタンス、またはどちらもnullの場合、xとyは等しいものとする
else if (x == null)
return -1; // xがnull、かつyがnull以外の場合、xはyより小さいものとする
else if (y == null)
return 1; // yがnull、かつxがnull以外の場合、xはyより大きいものとする
// どちらもnull以外の場合、IDプロパティの値で比較する
if (x.ID > y.ID)
return 1;
else if (x.ID < y.ID)
return -1;
else // if (x.ID == y.ID)
return 0;
}
引数にnullが渡される可能性のある比較メソッドの実装例
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
If x Is y Then
Return 0 ' 同一のインスタンス、またはどちらもNothingの場合、xとyは等しいものとする
Else If x Is Nothing Then
Return -1 ' xがNothing、かつyがNothing以外の場合、xはyより小さいものとする
Else If y Is Nothing Then
Return 1 ' yがNothing、かつxがNothing以外の場合、xはyより大きいものとする
End If
' どちらもNothing以外の場合、IDプロパティの値で比較する
If x.ID > y.ID Then
Return 1 ' xのIDがyのIDより大きい→xはyより大きい
Else If x.ID < y.ID
Return -1 ' xのIDがyのIDより小さい→xはyより小さい
Else ' If x.ID = y.ID
Return 0 ' xのIDとyのIDが等しい→xはyと等しい
End If
End Function
.NET Frameworkにおける文字列型(Stringクラス)では、null/Nothingは他のいずれの値よりも小さい、またnull/Nothing同士は等しいものとして比較が行われるため、上記の例もこれに準じた結果を返すようにしています。
以下は上記のように定義した比較メソッドを使ってnull/Nothingを含むコレクションをソートする例です。
List.Sortメソッドでnullを含むコレクションをソートする
using System;
using System.Collections.Generic;
class Account {
public int ID;
public string Name;
public Account(int id, string name)
{
this.ID = id;
this.Name = name;
}
}
class Sample {
// IDプロパティの値にしたがってAccountクラスの比較を行うメソッド
static int CompareAccount(Account x, Account y)
{
if (x == y)
return 0; // 同一のインスタンス、またはどちらもnullの場合、xとyは等しいものとする
else if (x == null)
return -1; // xがnull、かつyがnull以外の場合、xはyより小さいものとする
else if (y == null)
return 1; // yがnull、かつxがnull以外の場合、xはyより大きいものとする
// どちらもnull以外の場合、IDプロパティの値で比較する
if (x.ID > y.ID)
return 1;
else if (x.ID < y.ID)
return -1;
else // if (x.ID == y.ID)
return 0;
}
static void Main()
{
// 要素にnullを含むコレクション
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob"),
new Account(1, "Dave"),
new Account(2, "Alice"),
null,
new Account(5, "Charlie"),
null,
new Account(4, "Eve"),
});
// 比較用のメソッドを指定してソート
list.Sort(CompareAccount);
foreach (Account a in list) {
if (a == null)
Console.WriteLine("(null)");
else
Console.WriteLine("{0} {1}", a.ID, a.Name);
}
}
}
List.Sortメソッドでnullを含むコレクションをソートする
Imports System
Imports System.Collections.Generic
Class Account
Public ID As Integer
Public Name As String
Public Sub New(ByVal id As Integer, ByVal name As String)
MyClass.ID = id
MyClass.Name = name
End Sub
End Class
Class Sample
' IDプロパティの値にしたがってAccountクラスの比較を行うメソッド
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
If x Is y Then
Return 0 ' 同一のインスタンス、またはどちらもNothingの場合、xとyは等しいものとする
Else If x Is Nothing Then
Return -1 ' xがNothing、かつyがNothing以外の場合、xはyより小さいものとする
Else If y Is Nothing Then
Return 1 ' yがNothing、かつxがNothing以外の場合、xはyより大きいものとする
End If
' どちらもNothing以外の場合、IDプロパティの値で比較する
If x.ID > y.ID Then
Return 1 ' xのIDがyのIDより大きい→xはyより大きい
Else If x.ID < y.ID
Return -1 ' xのIDがyのIDより小さい→xはyより小さい
Else ' If x.ID = y.ID
Return 0 ' xのIDとyのIDが等しい→xはyと等しい
End If
End Function
Shared Sub Main()
' 要素にNothingを含むコレクション
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob"), _
New Account(1, "Dave"), _
New Account(2, "Alice"), _
Nothing, _
New Account(5, "Charlie"), _
Nothing, _
New Account(4, "Eve") _
})
' 比較用のメソッドを指定してソート
list.Sort(AddressOf CompareAccount)
For Each a As Account In list
If a Is Nothing Then
Console.WriteLine("(Nothing)")
Else
Console.WriteLine("{0} {1}", a.ID, a.Name)
End If
Next
End Sub
End Class
実行結果
(null) (null) 1 Dave 2 Alice 3 Bob 4 Eve 5 Charlie
このように、昇順の場合はnull/Nothingが前の方へ並べ替えられます。 後ろの方へ並べ替えたい場合は、比較メソッドを変更してnull/Nothingは他のいずれの値よりも大きいと定義することによって実現できます。
OrderBy
複合型は1つ以上の基本型から構成されるため、複合型のソートで実際にキーとして選ばれるのは単純型のメンバとなります。 また、単純型のソートの場合でも、単に昇順・降順でのソートで十分な場合がほとんどで、独自の並び替え順序が必要になる事はそう多くありません。
OrderByメソッドは、複合型をソートしたい場合でもキーとなるメンバを選択するだけでソートすることが出来、また選択したキーが単純型であれば並べ替え順序を定義する必要もないため、より少ない記述でソートを行うことが出来ます。
OrderByメソッドの詳細とキーの選択については基本型のソートと昇順・降順でのソート §.OrderByメソッドとキーの選択で解説しているので省略しますが、先に挙げた例をList.SortではなくOrderByメソッドでソートするように変えると、以下のようになります。
OrderByメソッドを使って複合型のコレクションをソートする
using System;
using System.Collections.Generic;
using System.Linq;
class Account {
public int ID;
public string Name;
public Account(int id, string name)
{
this.ID = id;
this.Name = name;
}
}
class Sample {
static void Main()
{
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob"),
new Account(1, "Dave"),
new Account(2, "Alice"),
new Account(5, "Charlie"),
new Account(4, "Eve"),
});
// IDでソート(IDフィールドをソート時のキーとしてOrderByで並べ替える)
IOrderedEnumerable<Account> sorted = list.OrderBy(a => a.ID);
// Nameでソートする場合(Nameフィールドをソート時のキーとしてOrderByで並べ替える)
//IOrderedEnumerable<Account> sorted = list.OrderBy(a => a.Name);
foreach (Account a in sorted) {
Console.WriteLine("{0} {1}", a.ID, a.Name);
}
}
}
OrderByメソッドを使って複合型のコレクションをソートする
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Account
Public ID As Integer
Public Name As String
Public Sub New(ByVal id As Integer, ByVal name As String)
MyClass.ID = id
MyClass.Name = name
End Sub
End Class
Class Sample
Shared Sub Main()
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob"), _
New Account(1, "Dave"), _
New Account(2, "Alice"), _
New Account(5, "Charlie"), _
New Account(4, "Eve") _
})
' IDでソート(IDフィールドをソート時のキーとしてOrderByで並べ替える)
Dim sorted As IOrderedEnumerable(Of Account) = list.OrderBy(Function(a) a.ID)
' Nameでソートする場合(Nameフィールドをソート時のキーとしてOrderByで並べ替える)
'Dim sorted As IOrderedEnumerable(Of Account) = list.OrderBy(Function(a) a.Name)
For Each a As Account In sorted
Console.WriteLine("{0} {1}", a.ID, a.Name)
Next
End Sub
End Class
実行結果
1 Dave 2 Alice 3 Bob 4 Eve 5 Charlie
OrderByメソッドの代わりにOrderByDescendingメソッドを使うことにより、降順でソートすることが出来ます。
null/Nothingの考慮
OrderByメソッドではキーの選択を行ってソートを行います。 コレクション内の要素がnull/Nothingだった場合にはキーとして使う値を参照しようとしてもヌル参照となるため、ソートを継続することができません。 そのため、ソートしたい対象が参照型のコレクションで、かつコレクションにnull/Nothingが含まれる可能性がある場合は、要素がnull/Nothingだった場合の考慮を行う必要があります。
具体的には、次のようにして非nullの要素のみをソートするようにします。
- コレクション内の要素のうち、nullの要素とそうでないものを分ける (Whereメソッド)
- 非nullの要素のみソートを行う (OrderByメソッド)
- nullの要素と、ソートした非nullの要素を結合する (Concatメソッド)
以下は上記のようにしてnull/Nothingを含むコレクションをソートする例です。
OrderByメソッドでnullを含むコレクションをソートする
using System;
using System.Collections.Generic;
using System.Linq;
class Account {
public int ID;
public string Name;
public Account(int id, string name)
{
this.ID = id;
this.Name = name;
}
}
class Sample {
static void Main()
{
// 要素にnullを含むコレクション
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob"),
new Account(1, "Dave"),
new Account(2, "Alice"),
null,
new Account(5, "Charlie"),
null,
new Account(4, "Eve"),
});
// コレクションのうち、nullの要素のみを取得する
IEnumerable<Account> nulls = list.Where(a => a == null);
// コレクションのうち、非nullの要素のみを取得する
IEnumerable<Account> nonNulls = list.Where(a => a != null);
// nullの要素と、ソートした非nullの要素を結合する
IEnumerable<Account> sorted = nulls.Concat(nonNulls.OrderBy(a => a.ID));
foreach (Account a in sorted) {
if (a == null)
Console.WriteLine("(null)");
else
Console.WriteLine("{0} {1}", a.ID, a.Name);
}
}
}
OrderByメソッドでnullを含むコレクションをソートする
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Account
Public ID As Integer
Public Name As String
Public Sub New(ByVal id As Integer, ByVal name As String)
MyClass.ID = id
MyClass.Name = name
End Sub
End Class
Class Sample
Shared Sub Main()
' 要素にNothingを含むコレクション
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob"), _
New Account(1, "Dave"), _
New Account(2, "Alice"), _
Nothing, _
New Account(5, "Charlie"), _
Nothing, _
New Account(4, "Eve") _
})
' コレクションのうち、Nothingの要素のみを取得する
Dim nulls As IEnumerable(Of Account) = list.Where(Function(a) a Is Nothing)
' コレクションのうち、非Nothingの要素のみを取得する
Dim nonNulls As IEnumerable(Of Account) = list.Where(Function(a) a IsNot Nothing)
' Nothingの要素と、ソートした非Nothingの要素を結合する
Dim sorted As IEnumerable(Of Account) = nulls.Concat(nonNulls.OrderBy(Function(a) a.ID))
For Each a As Account In sorted
If a Is Nothing Then
Console.WriteLine("(Nothing)")
Else
Console.WriteLine("{0} {1}", a.ID, a.Name)
End If
Next
End Sub
End Class
実行結果
(null) (null) 1 Dave 2 Alice 3 Bob 4 Eve 5 Charlie
この例ではnull/Nothingを先に結合しているため、null/Nothingが前の方へ並べ替えられます。 後ろの方へ並べ替えたい場合は、次のように結合順序を逆にすることで実現できます。
OrderByメソッドでnullを後ろの方へ並べるようにソートする
// ソートした非nullの要素の後にnullの要素を結合する
IEnumerable<Account> sorted = nonNulls.OrderBy(a => a.ID).Concat(nulls);
OrderByメソッドでnullを後ろの方へ並べるようにソートする
' ソートした非Nothingの要素の後にNothingの要素を結合する
Dim sorted As IEnumerable(Of Account) = nonNulls.OrderBy(Function(a) a.ID).Concat(nulls)
複数キーでのソート
ここでは複数のキーでソートする場合についてを扱います。 たとえば、次のようなデータがあったときに、まずAge(年齢)の若い順に並べ替え、Ageが同じ場合はIDが小さい順に並べ替えたいといった場合です。 言い換えると、Ageを第一のキー、IDを第二のキーとしてソートするための方法です。
| ID | Name | Age |
| 3 | Bob | 16 |
| 1 | Dave | 25 |
| 2 | Alice | 16 |
| 5 | Charlie | 9 |
| 4 | Eve | 16 |
| 6 | Romeo | 9 |
| 7 | Juliet | 25 |
→ソート→
| ID | Name | Age |
| 5 | Charlie | 9 |
| 6 | Romeo | 9 |
| 2 | Alice | 16 |
| 3 | Bob | 16 |
| 4 | Eve | 16 |
| 1 | Dave | 25 |
| 7 | Juliet | 25 |
Sort + Comparison<T>
これまでの例では、並べ替え順序を定義する際に単一のキーのみを用いていましたが、並べ替え順序の定義を拡張することで複数のキーでソートできるようになります。 複数のキーでソートするには、まず第一のキーで比較し、同じだった場合は第二のキーで比較するように並べ替え順序を定義することで実現できます。
まず、一つのキーでソートする場合について振り返ると、比較を行うメソッドでは引数として渡される二つの要素xとyについて、その大小関係に従って次のような値を返すように実装する必要がありました。
- x > y ならば 正の数
- x < y ならば 負の数
- x = y ならば 0
二つのキーでソートする場合は、要素xとyについてまず第一のキーで比較を行い、第一のキーが同じだった場合は第二のキーで比較するようにします。 つまり、上記の条件式を拡張して、比較を行うメソッドでは次のような値を返すように実装します。
- 第一のキーについて x > y (x.Key1 > y.Key1) ならば 正の数
- 第一のキーについて x < y (x.Key1 < y.Key1) ならば 負の数
- 第一のキーについて x = y (x.Key1 = y.Key1) ならば さらに第二のキーで比較する
- 第二のキーについて x > y (x.Key2 > y.Key2) ならば 正の数
- 第二のキーについて x < y (x.Key2 < y.Key2) ならば 負の数
- 第二のキーについて x < y (x.Key2 = y.Key2) ならば 0
このようにすることで、各要素はまず第一のキーの順に並べ替えられ、第一のキーが同じ要素については第二のキーの順に並べ替えられるようになり、二つのキーでソートされることになります。
具体例を見ていきます。 次の例では、ID(int)、名前(string)、年齢(int)のフィールドを持つAccountクラスとそれを格納するリストを作成し、ソートしています。 ここでは第一のキーを年齢、第二のキーをIDとし、年齢が若い順、年齢が同じ場合はIDが小さい順にソートしています。
Sortメソッドで複数キーのソートを行う
using System;
using System.Collections.Generic;
class Account {
public int ID;
public string Name;
public int Age;
public Account(int id, string name, int age)
{
this.ID = id;
this.Name = name;
this.Age = age;
}
}
class Sample {
static int CompareAccount(Account x, Account y)
{
// 第一のキー(Ageフィールド)で比較
if (x.Age > y.Age) {
return 1;
}
else if (x.Age < y.Age) {
return -1;
}
else /* if (x.Age == y.Age) */ {
// 第一のキーが同じだった場合は、第二のキー(IDフィールド)で比較
if (x.ID > y.ID)
return 1;
else if (x.ID < y.ID)
return -1;
else // if (x.ID == y.ID)
return 0;
}
}
static void Main()
{
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob", 16),
new Account(1, "Dave", 25),
new Account(2, "Alice", 16),
new Account(5, "Charlie", 9),
new Account(4, "Eve", 16),
new Account(6, "Romeo", 9),
new Account(7, "Juliet", 25),
});
// ソート
list.Sort(CompareAccount);
foreach (Account a in list) {
Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age);
}
}
}
Sortメソッドで複数キーのソートを行う
Imports System
Imports System.Collections.Generic
Class Account
Public ID As Integer
Public Name As String
Public Age As Integer
Public Sub New(ByVal id As Integer, ByVal name As String, ByVal age As Integer)
MyClass.ID = id
MyClass.Name = name
Myclass.Age = age
End Sub
End Class
Class Sample
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
' 第一のキー(Ageフィールド)で比較
If x.Age > y.Age Then
Return 1
Else If x.Age < y.Age Then
Return -1
Else ' If x.Age = y.Age Then
' 第一のキーが同じだった場合は、第二のキー(IDフィールド)で比較
If x.ID > y.ID Then
Return 1
Else If x.ID < y.ID Then
Return -1
Else ' If x.ID = y.ID Then
Return 0
End If
End If
End Function
Shared Sub Main()
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob", 16), _
New Account(1, "Dave", 25), _
New Account(2, "Alice", 16), _
New Account(5, "Charlie", 9), _
New Account(4, "Eve", 16), _
New Account(6, "Romeo", 9), _
New Account(7, "Juliet", 25) _
})
' ソート
list.Sort(AddressOf CompareAccount)
For Each a As Account In list
Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age)
Next
End Sub
End Class
実行結果
5 Charlie 9 6 Romeo 9 2 Alice 16 3 Bob 16 4 Eve 16 1 Dave 25 7 Juliet 25
次に上記の例を少し変えて、名前を第一のキー、IDを第二のキーとしてソートしてみます。 文字列の比較にはString.Compareメソッドが使えます。 このメソッドも引数の大小関係に応じて正の数・負の数・0のいずれかが返されます。 同じ場合には0となるので、戻り値が0の場合は第二のキーで比較するようにします。
Sortメソッドで複数キーのソートを行う(第一キーと第二キーの順序を替えたもの)
using System;
using System.Collections.Generic;
class Account {
public int ID;
public string Name;
public int Age;
public Account(int id, string name, int age)
{
this.ID = id;
this.Name = name;
this.Age = age;
}
}
class Sample {
static int CompareAccount(Account x, Account y)
{
// 第一のキー(Nameフィールド)で比較
int compareName = string.Compare(x.Name, y.Name);
if (compareName == 0) {
// x.Name == y.Nameだった場合、第二のキー(IDフィールド)で比較する
if (x.ID > y.ID)
return 1;
else if (x.ID < y.ID)
return -1;
else // if (x.ID == y.ID)
return 0;
}
else {
// x.Name > y.Nameもしくはx.Name < y.Nameだった場合、比較結果をそのまま返す
return compareName;
}
}
static void Main()
{
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Alice", 16),
new Account(1, "Bob", 25),
new Account(2, "Alice", 16),
new Account(5, "Charlie", 9),
new Account(4, "Bob", 16),
new Account(6, "Alice", 9),
new Account(7, "Charlie", 25),
});
// ソート
list.Sort(CompareAccount);
foreach (Account a in list) {
Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age);
}
}
}
Sortメソッドで複数キーのソートを行う(第一キーと第二キーの順序を替えたもの)
Imports System
Imports System.Collections.Generic
Class Account
Public ID As Integer
Public Name As String
Public Age As Integer
Public Sub New(ByVal id As Integer, ByVal name As String, ByVal age As Integer)
MyClass.ID = id
MyClass.Name = name
Myclass.Age = age
End Sub
End Class
Class Sample
Shared Function CompareAccount(ByVal x As Account, ByVal y As Account) As Integer
' 第一のキー(Nameフィールド)で比較
Dim compareName As Integer = String.Compare(x.Name, y.Name)
If compareName = 0 Then
' x.Name = y.Nameだった場合、第二のキー(IDフィールド)で比較する
If x.ID > y.ID Then
Return 1
Else If x.ID < y.ID Then
Return -1
Else ' If x.ID = y.ID Then
Return 0
End If
Else
' x.Name > y.Nameもしくはx.Name < y.Nameだった場合、比較結果をそのまま返す
Return compareName
End If
End Function
Shared Sub Main()
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Alice", 16), _
New Account(1, "Bob", 25), _
New Account(2, "Alice", 16), _
New Account(5, "Charlie", 9), _
New Account(4, "Bob", 16), _
New Account(6, "Alice", 9), _
New Account(7, "Charlie", 25) _
})
' ソート
list.Sort(AddressOf CompareAccount)
For Each a As Account In list
Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age)
Next
End Sub
End Class
実行結果
2 Alice 16 3 Alice 16 6 Alice 9 1 Bob 25 4 Bob 16 5 Charlie 9 7 Charlie 25
ここまではキーが二つの場合を例示しましたが、さらに多くのキーでソートしたければ、第二のキーで比較して同じなら第三のキー、第三のキーで比較して同じなら第四のキーと、比較処理を次々拡張することで実現できます。
OrderBy + ThenBy
OrderByメソッドのみを使ったソートでは単一のキーでしかソート出来ませんが、ThenByメソッドと組み合わせて使うと、複数のキーでのソートが出来るようになります。
ThenByメソッドは、OrderByメソッドの戻り値であるIOrderedEnumerable<TSource>に対する拡張メソッドであり、OrderByメソッドの結果(単一のキーでソートした結果)に対してThenByメソッドを呼び出すことにより、第二のキーでソートした結果を得ることが出来ます。
早速、具体例を見ていきます。 次の例では、ID(int)、名前(string)、年齢(int)のフィールドを持つAccountクラスとそれを格納するリストを作成し、ソートしています。 ここでは第一のキーを年齢、第二のキーをIDとし、年齢が若い順、年齢が同じ場合はIDが小さい順にソートしています。
OrderBy+ThenByメソッドで複数キーのソートを行う
using System;
using System.Collections.Generic;
using System.Linq;
class Account {
public int ID;
public string Name;
public int Age;
public Account(int id, string name, int age)
{
this.ID = id;
this.Name = name;
this.Age = age;
}
}
class Sample {
static void Main()
{
List<Account> list = new List<Account>(new Account[] {
new Account(3, "Bob", 16),
new Account(1, "Dave", 25),
new Account(2, "Alice", 16),
new Account(5, "Charlie", 9),
new Account(4, "Eve", 16),
new Account(6, "Romeo", 9),
new Account(7, "Juliet", 25),
});
// ソート
// (AgeをキーとしてOrderByにより並べ替え、その結果をさらにIDをキーとしてThenByで並べ替える)
IOrderedEnumerable<Account> sorted = list.OrderBy(a => a.Age).ThenBy(a => a.ID);
foreach (Account a in sorted) {
Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age);
}
}
}
OrderBy+ThenByメソッドで複数キーのソートを行う
Imports System
Imports System.Collections.Generic
Class Account
Public ID As Integer
Public Name As String
Public Age As Integer
Public Sub New(ByVal id As Integer, ByVal name As String, ByVal age As Integer)
MyClass.ID = id
MyClass.Name = name
Myclass.Age = age
End Sub
End Class
Class Sample
Shared Sub Main()
Dim list As New List(Of Account)(New Account() { _
New Account(3, "Bob", 16), _
New Account(1, "Dave", 25), _
New Account(2, "Alice", 16), _
New Account(5, "Charlie", 9), _
New Account(4, "Eve", 16), _
New Account(6, "Romeo", 9), _
New Account(7, "Juliet", 25) _
})
' ソート
' (AgeをキーとしてOrderByにより並べ替え、その結果をさらにIDをキーとしてThenByで並べ替える)
Dim sorted As IOrderedEnumerable(Of Account) = list.OrderBy(Function(a) a.Age).ThenBy(Function(a) a.ID)
For Each a As Account In sorted
Console.WriteLine("{0} {1,-8} {2}", a.ID, a.Name, a.Age)
Next
End Sub
End Class
実行結果
5 Charlie 9 6 Romeo 9 2 Alice 16 3 Bob 16 4 Eve 16 1 Dave 25 7 Juliet 25
さらに、ThenByメソッドの戻り値もIOrderedEnumerable<TSource>であるため、ThenByメソッドの戻り値に対してThenByメソッドを呼び出すと、第三のキーでソートした結果を得られるようになります。 このように、キーの数に応じてThenByメソッドを続けて呼び出すことで複数キーでのソートを行うことが出来ます。
OrderByメソッドと同様、ThenByメソッドも遅延実行されるため、戻り値に対してforeach等で列挙操作を行うことで初めてソートが行われる点に注意してください。
ソートと遅延実行に関する注意点については基本型のソートと昇順・降順でのソート §.元のコレクションに対する変更とOrderByメソッドの結果への影響を参照してください。
パフォーマンスの比較
ここではソートを行ういくつかのケースについてパフォーマンスの比較を行った結果を紹介します。 比較メソッドの定義方法やソートするデータの種類等によっては結果が変わるので、ここで紹介している結果はあくまで参考程度のものです。
Sort vs OrderBy
複数のキーでソートするのに、Sort(Comparison<T>)メソッドを使った場合とOrderByメソッド+ThenByメソッドを使った場合を比較すると、速度の点では大きな差は無いようです。 以下のコードでは、先と同様100個、10,000個、1,000,000個の要素を持つList<Tuple<int, int>>に対してSort(Comparison<T>)メソッドとOrderByメソッド+ThenByメソッドでソートし、列挙する操作をそれぞれ3回試行した場合の経過時間を比較しています。
検証に使ったコード
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
class Sample {
static void Main()
{
Console.WriteLine(Environment.OSVersion);
Console.WriteLine(Environment.Version);
foreach (var count in new[] {100, 10 * 1000, 1000 * 1000}) {
Console.WriteLine("{0:N0}", count);
for (var i = 0; i < 3; i++) {
TestSortComparison(CreateSource(count, i));
TestOrderByThenBy(CreateSource(count, i));
}
}
}
static List<Tuple<int, int>> CreateSource(int count, int seed)
{
var rand = new Random(seed);
var list = new List<Tuple<int, int>>();
for (var i = 0; i < count; i++) {
list.Add(Tuple.Create(rand.Next(), rand.Next()));
}
return list;
}
static int Compare(Tuple<int, int> x, Tuple<int, int> y)
{
var ret = x.Item1 - y.Item1;
return ret == 0 ? x.Item2 - y.Item2 : ret;
}
static void TestSortComparison(List<Tuple<int, int>> source)
{
var sw = Stopwatch.StartNew();
source.Sort(Compare);
foreach (var val in source) {
}
sw.Stop();
Console.WriteLine(" Sort(Comparison<T>): {0}", sw.Elapsed);
}
static void TestOrderByThenBy(List<Tuple<int, int>> source)
{
var sw = Stopwatch.StartNew();
foreach (var val in source.OrderBy(val => val.Item1).ThenBy(val => val.Item2)) {
}
sw.Stop();
Console.WriteLine(" OrderBy + ThenBy : {0}", sw.Elapsed);
}
}
実行結果 (Windows 7 + .NET Framework 4)
Microsoft Windows NT 6.1.7601 Service Pack 1 4.0.30319.239 100 Sort(Comparison<T>): 00:00:00.0016116 OrderBy + ThenBy : 00:00:00.0128862 Sort(Comparison<T>): 00:00:00.0000396 OrderBy + ThenBy : 00:00:00.0000497 Sort(Comparison<T>): 00:00:00.0000282 OrderBy + ThenBy : 00:00:00.0000357 10,000 Sort(Comparison<T>): 00:00:00.0039588 OrderBy + ThenBy : 00:00:00.0056537 Sort(Comparison<T>): 00:00:00.0045002 OrderBy + ThenBy : 00:00:00.0042474 Sort(Comparison<T>): 00:00:00.0038242 OrderBy + ThenBy : 00:00:00.0048581 1,000,000 Sort(Comparison<T>): 00:00:01.0339300 OrderBy + ThenBy : 00:00:01.4343420 Sort(Comparison<T>): 00:00:01.0314824 OrderBy + ThenBy : 00:00:01.2782487 Sort(Comparison<T>): 00:00:01.0515235 OrderBy + ThenBy : 00:00:01.5493575
実行結果 (Ubuntu 11.10 + Mono 2.10.6)
Unix 3.0.0.14 4.0.30319.1 100 Sort(Comparison<T>): 00:00:00.0013989 OrderBy + ThenBy : 00:00:00.0164684 Sort(Comparison<T>): 00:00:00.0000365 OrderBy + ThenBy : 00:00:00.0000487 Sort(Comparison<T>): 00:00:00.0000362 OrderBy + ThenBy : 00:00:00.0000495 10,000 Sort(Comparison<T>): 00:00:00.0070140 OrderBy + ThenBy : 00:00:00.0058386 Sort(Comparison<T>): 00:00:00.0063343 OrderBy + ThenBy : 00:00:00.0051259 Sort(Comparison<T>): 00:00:00.0065034 OrderBy + ThenBy : 00:00:00.0058673 1,000,000 Sort(Comparison<T>): 00:00:01.3199098 OrderBy + ThenBy : 00:00:01.1463424 Sort(Comparison<T>): 00:00:01.2777875 OrderBy + ThenBy : 00:00:01.1191267 Sort(Comparison<T>): 00:00:01.2825583 OrderBy + ThenBy : 00:00:01.1213952
単一のキーでソートした場合の結果については、基本型のソートと昇順・降順でのソート §.パフォーマンスの比較を参照してください。