ここでは、配列・List・Dictionaryなどの各種コレクションを使ったデータの並べ替え、ソート(sort)について解説します。 ソートするにはどのようにすればよいかを主眼に置くため、ここでは数値型や文字列型などの単純型(基本型)からなるコレクションのソートのみを扱います。 ソートしたい対象が決まっていて、そのソート方法を知りたい場合は以下の項を参照してください。
- 配列をソートしたい
- →§.配列のソート (Array.Sort)
- Listをソートしたい
- →§.Listのソート (List.Sort)
- Dictionaryをソートしたい
- →§.Dictionaryのソート
- 降順でソートしたい
ソート順を逆にしたい - →§.降順でのソート
上記のようなソートのメソッドについては既に知っていて、その上でソートの動作を詳細にカスタマイズしたり、基本型以外の型をソートしたいといった場合には、ソート対象やソートの目的に応じて以下の文章を参照してください。
ソート
ここでは、配列・List・Dictionaryなどを使ったデータの並べ替えについて見ていきます。 まずは昇順(小さい順)でソートする方法について解説します。 降順(大きい順)でのソート方法については追って解説します。
配列のソート (Array.Sort)
配列をソートするには、Array.Sortメソッドを使います。 このメソッドは静的メソッドで、引数に指定された配列をソートします。
using System;
class Sample {
static void Main()
{
// ソート対象の配列
var arr = new int[] {5, 2, 3, 1, 4};
// ソート
Array.Sort(arr);
// ソート結果を表示
foreach (var val in arr) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Class Sample
Shared Sub Main()
' ソート対象の配列
Dim arr() As Integer = New Integer() {5, 2, 3, 1, 4}
' ソート
Array.Sort(arr)
' ソート結果の表示
For Each val As Integer In arr
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
1, 2, 3, 4, 5,
using System;
class Sample {
static void Main()
{
// ソート対象の配列
var arr = new string[] {"ab", "abc", "aa", "a", "b", "acb"};
// ソート
Array.Sort(arr);
// ソート結果を表示
foreach (var val in arr) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Class Sample
Shared Sub Main()
' ソート対象の配列
Dim arr() As String = New String() {"ab", "abc", "aa", "a", "b", "acb"}
' ソート
Array.Sort(arr)
' ソート結果を表示
For Each val As String In arr
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
a, aa, ab, abc, acb, b,
Array.Sortメソッドでは、引数に指定された配列自体をソートします(破壊的変更)。 ソートされた配列が新たに作成され戻り値として返されることはありません。 そのため、ソート前の状態も維持しておきたい場合は、Array.Cloneメソッドなどを使ってあらかじめ配列の複製を作っておき、その後で変更用の配列をソートする必要があります。
非破壊的なソートを行いたい場合はEnumerable.OrderByメソッドを使うことができます。
特に順序を指定しない限り、Array.Sortメソッドはデフォルトのソート順でソートします。 デフォルトのソート順については基本型とデフォルトのソート順、ソート順の定義については大小関係の定義と比較で解説しています。 逆順でのソートについては§.降順でのソートで後述しています。
ジャグ配列・多次元配列のソートについてはジャグ配列・多次元配列のソートで解説します。
独自に定義した型は通常そのままではソートできません。 この場合、ソートができないことを表す例外InvalidOperationExceptionがスローされます。
using System;
// 独自に定義した型
class Account {
public string Name;
public Account(string name)
{
this.Name = name;
}
}
class Sample {
static void Main()
{
// ソート対象の配列
var arr = new Account[] {new Account("Bob"), new Account("Alice"), new Account("Charlie")};
// ソート
Array.Sort(arr);
}
}
Imports System
' 独自に定義した型
Class Account
Public Name As String
Public Sub New(ByVal name As String)
Me.Name = name
ENd Sub
End Class
Class Sample
Shared Sub Main()
' ソート対象の配列
Dim arr() As Account = New Account() {New Account("Bob"), New Account("Alice"), New Account("Charlie")}
' ソート
Array.Sort(arr)
End Sub
End Class
System.InvalidOperationException: 配列にある 2 つの要素を比較できませんでした。 ---> System.ArgumentException: 少なくとも 1 つのオブジェクトで IComparable を実装しなければなりません。 場所 System.Collections.Comparer.Compare(Object a, Object b) 場所 System.Collections.Generic.ObjectComparer`1.Compare(T x, T y) 場所 System.Collections.Generic.ArraySortHelper`1.SwapIfGreaterWithItems(T[] keys, IComparer`1 comparer, Int32 a, Int32 b) 場所 System.Collections.Generic.ArraySortHelper`1.QuickSort(T[] keys, Int32 left, Int32 right, IComparer`1 comparer) 場所 System.Collections.Generic.ArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) --- 内部例外スタック トレースの終わり --- 場所 System.Collections.Generic.ArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) 場所 System.Array.Sort[T](T[] array, Int32 index, Int32 length, IComparer`1 comparer) 場所 System.Array.Sort[T](T[] array) 場所 Sample.Main()
これはソート対象の大小関係が定義されていないために発生します。 ソートを行うためにはソート対象の大小関係が比較できなければなりませんが、上記の例ではAccountクラスの大小関係がどこにも定義されておらず比較ができないため、ソートの際に例外が発生しています。
Array.Sortメソッドでソートを行うには、ソート対象の型にIComparable<T>(またはIComparable)インターフェイスを実装するか、あるいはSortメソッドの引数にIComparer<T>(またはIComparer)インターフェイス、もしくはComparison<T>デリゲートを指定する必要があります。
詳しくは複合型のソート・複数キーでのソートを参照してください。 また個々のインターフェイスとその実装方法については大小関係の定義と比較を参照してください。
Listのソート (List.Sort)
List<T>をソートするには、List.Sortメソッドを使います。 List.Sortメソッドはメソッドを呼び出したインスタンス自身をソートします。
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// ソート対象のList<int>
var list = new List<int>(new int[] {5, 2, 3, 1, 4});
// ソート
list.Sort();
// ソート結果を表示
foreach (var val in list) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' ソート対象のList(Of Integer)
Dim list As New List(Of Integer)(New Integer() {5, 2, 3, 1, 4})
' ソート
list.Sort()
' ソート結果を表示
For Each val As Integer In list
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
1, 2, 3, 4, 5,
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// ソート対象のList<string>
var list = new List<string>(new string[] {"ab", "abc", "aa", "a", "b", "acb"});
// ソート
list.Sort();
// ソート結果を表示
foreach (var val in list) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' ソート対象のList(Of String)
Dim list As New List(Of String)(New String() {"ab", "abc", "aa", "a", "b", "acb"})
' ソート
list.Sort()
' ソート結果を表示
For Each val As String In list
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
a, aa, ab, abc, acb, b,
List.Sortメソッドでは、インスタンス自身をソートします(破壊的変更)。 ソートされたListが新たに作成され戻り値として返されることはありません。 そのため、ソート前の状態も維持しておきたい場合は、あらかじめListの複製を作っておき(ジェネリックコレクション(1) List §.Listの複製)、その後で変更用のListをソートする必要があります。
非破壊的なソートを行いたい場合はEnumerable.OrderByメソッドを使うことができます。
特に順序を指定しない限り、List.Sortメソッドはデフォルトのソート順でソートします。 デフォルトのソート順については基本型とデフォルトのソート順、ソート順の定義については大小関係の定義と比較で解説しています。 逆順でのソートについては§.降順でのソートで後述しています。
独自に定義した型は通常そのままではソートできません。 この場合、ソートができないことを表す例外InvalidOperationExceptionがスローされます。
using System;
using System.Collections.Generic;
// 独自に定義した型
class Account {
public string Name;
public Account(string name)
{
this.Name = name;
}
}
class Sample {
static void Main()
{
// ソート対象のList
var list = new List<Account>(new Account[] {new Account("Bob"), new Account("Alice"), new Account("Charlie")});
// ソート
list.Sort();
}
}
Imports System
Imports System.Collections.Generic
' 独自に定義した型
Class Account
Public Name As String
Public Sub New(ByVal name As String)
Me.Name = name
ENd Sub
End Class
Class Sample
Shared Sub Main()
' ソート対象のList
Dim list As New List(Of Account)(New Account() {New Account("Bob"), New Account("Alice"), New Account("Charlie")})
' ソート
list.Sort()
End Sub
End Class
System.InvalidOperationException: 配列にある 2 つの要素を比較できませんでした。 ---> System.ArgumentException: 少なくとも 1 つのオブジェクトで IComparable を実装しなければなりません。 場所 System.Collections.Comparer.Compare(Object a, Object b) 場所 System.Collections.Generic.ObjectComparer`1.Compare(T x, T y) 場所 System.Collections.Generic.ArraySortHelper`1.SwapIfGreaterWithItems(T[] keys, IComparer`1 comparer, Int32 a, Int32 b) 場所 System.Collections.Generic.ArraySortHelper`1.QuickSort(T[] keys, Int32 left, Int32 right, IComparer`1 comparer) 場所 System.Collections.Generic.ArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) --- 内部例外スタック トレースの終わり --- 場所 System.Collections.Generic.ArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) 場所 System.Array.Sort[T](T[] array, Int32 index, Int32 length, IComparer`1 comparer) 場所 System.Collections.Generic.List`1.Sort(Int32 index, Int32 count, IComparer`1 comparer) 場所 Sample.Main()
これはソート対象の大小関係が定義されていないために発生します。 ソートを行うためにはソート対象の大小関係が比較できなければなりませんが、上記の例ではAccountクラスの大小関係がどこにも定義されておらず比較ができないため、ソートの際に例外が発生しています。
List.Sortメソッドでソートを行うには、ソート対象の型にIComparable<T>(またはIComparable)インターフェイスを実装するか、あるいはSortメソッドの引数にIComparer<T>(またはIComparer)インターフェイス、もしくはComparison<T>デリゲートを指定する必要があります。
詳しくは複合型のソート・複数キーでのソートを参照してください。 また個々のインターフェイスとその実装方法については大小関係の定義と比較を参照してください。
ArrayListのソート (ArrayList.Sort)
ArrayListをソートするには、ArrayList.Sortメソッドを使います。 使い方・動作と結果はList<T>.Sortと同様です。
using System;
using System.Collections;
class Sample {
static void Main()
{
// ソート対象のArrayList
var list = new ArrayList(new int[] {5, 2, 3, 1, 4});
// ソート
list.Sort();
// ソート結果を表示
foreach (var val in list) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections
Class Sample
Shared Sub Main()
' ソート対象のArrayList
Dim list As New ArrayList(New Integer() {5, 2, 3, 1, 4})
' ソート
list.Sort()
' ソート結果を表示
For Each val As Integer In list
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
1, 2, 3, 4, 5,
using System;
using System.Collections;
class Sample {
static void Main()
{
// ソート対象のArrayList
var list = new ArrayList(new string[] {"ab", "abc", "aa", "a", "b", "acb"});
// ソート
list.Sort();
// ソート結果を表示
foreach (var val in list) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections
Class Sample
Shared Sub Main()
' ソート対象のArrayList
Dim list As New ArrayList(New String() {"ab", "abc", "aa", "a", "b", "acb"})
' ソート
list.Sort()
' ソート結果を表示
For Each val As String In list
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
a, aa, ab, abc, acb, b,
ArrayListを使う以外の方法がないなど、特に理由が無い限りはArrayListではなくList等を用いることが推奨されます。
SortedList, SortedDictionaryのソート
SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>では、要素を格納した時点で自動的にソートされるため、明示的にソートを行うメソッドはありません。 SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>では、キー(TKey)の値を基準にソートされます。
以下の例ではSortedListを使用していますが、SortedDictionaryでも結果は同様です。
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// ソート対象のSortedList<int, string>
SortedList<int, string> list = new SortedList<int, string>();
list.Add(2, "Alice");
list.Add(3, "Bob");
list.Add(5, "Charlie");
list.Add(1, "Dave");
list.Add(4, "Eve");
// SortedListの内容を列挙して表示
// (特にソートの操作を行わなくてもソート後の順序で表示される)
foreach (var pair in list) {
Console.WriteLine("{0} {1}", pair.Key, pair.Value);
}
}
}
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' ソート対象のSortedList(Of Integer, String)
Dim list As New SortedList(Of Integer, String)
list.Add(2, "Alice")
list.Add(3, "Bob")
list.Add(5, "Charlie")
list.Add(1, "Dave")
list.Add(4, "Eve")
' SortedListの内容を列挙して表示
' (特にソートの操作を行わなくてもソート後の順序で表示される)
For Each pair As KeyValuePair(Of Integer, String) In list
Console.WriteLine("{0} {1}", pair.Key, pair.Value)
Next
End Sub
End Class
1 Dave 2 Alice 3 Bob 4 Eve 5 Charlie
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// ソート対象のList<string>
SortedList<string, int> list = new SortedList<string, int>();
list.Add("Dave", 1);
list.Add("Alice", 2);
list.Add("Bob", 3);
list.Add("Eve", 4);
list.Add("Charlie", 5);
// SortedListの内容を列挙して表示
// (特にソートの操作を行わなくてもソート後の順序で表示される)
foreach (var pair in list) {
Console.WriteLine("{0} {1}", pair.Key, pair.Value);
}
}
}
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' ソート対象のSortedList(Of String, Integer)
Dim list As New SortedList(Of String, Integer)
list.Add("Dave", 1)
list.Add("Alice", 2)
list.Add("Bob", 3)
list.Add("Eve", 4)
list.Add("Charlie", 5)
' SortedListの内容を列挙して表示
' (特にソートの操作を行わなくてもソート後の順序で表示される)
For Each pair As KeyValuePair(Of String, Integer) In list
Console.WriteLine("{0} {1}", pair.Key, pair.Value)
Next
End Sub
End Class
Alice 2 Bob 3 Charlie 5 Dave 1 Eve 4
SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>で、値(TValue)の値を基準にソートする手段は用意されていないため、独自にソート処理を実装する必要があります。 詳しくはDictionaryのソートの解説を参照してください。
SortedList・SortedDictionaryのその他の機能と動作についてはジェネリックコレクション(3) SortedListとSortedDictionaryで詳しく解説しています。
Dictionaryのソート
Dictionary<TKey, TValue>には、SortedListとSortedDictionaryのように自動的に内容をソートする機能や、List.Sortのようにソートを行うメソッドは用意されていません。
ここでは、Dictionaryをソートする方法のいくつかを見ていきます。 Dictionary自体をソートすることは出来ないため、以下の方法はいずれも元のDictionaryの状態は変更せず、Dictionaryの内容を参照してソートされた状態で取得する方法(非破壊的なソート)となります。
常にソートされた状態にしておきたい場合はDictionaryではなくSortedList・SortedDictionaryを使用することが出来ますが、SortedList・SortedDictionaryでは要素の追加の度にソートされることによるオーバーヘッドが生じます。 これによる処理速度の低下を無視できないなどの理由がある場合は、やはりDictionaryを使い、必要になった時点でソートを行うという方法が必要になります。
KeyValuePairのリストに変換してソートする
1つ目は、Dictionaryの内容を、KeyValuePairのリストに変えてからソートする方法です。
Dictionary<string, int> | |
"Bob" | 3 |
"Dave" | 1 |
"Alice" | 2 |
"Charlie" | 5 |
"Eve" | 4 |
→ 変換 →
List<KeyValuePair<string, int>> | |
{"Bob", 3} | |
{"Dave", 1} | |
{"Alice", 2} | |
{"Charlie", 5} | |
{"Eve", 4} |
→ ソート →
List<KeyValuePair<string, int>> | |
{"Alice", 2} | |
{"Bob", 3} | |
{"Charlie", 5} | |
{"Dave", 1} | |
{"Eve", 4} |
KeyValuePairはDictionaryの内部で使われている構造体で、キーと値のペアを一つの構造体として格納するためのものです。 Dictionaryを直接列挙する場合などにも使われます。 DictionaryをこのKeyValuePairのリストに変換してから、List.Sortメソッドを使ってソートします。
ただし、ただ単にKeyValuePairをソートしようとしてもKeyValuePairはそのソート方法が定義されていないため、List.SortメソッドはInvalidOperationExceptionをスローします。 このため、KeyValuePairのソート方法(比較方法)を定義したメソッドを別途用意し、ソートする際にList.Sortメソッドに渡す必要があります。
この方法によるソートの具体例は次のようになります。 この例におけるCompareKeyValuePairメソッドが、KeyValuePairのソート方法(比較方法)を定義するメソッドです。
using System;
using System.Collections.Generic;
class Sample {
// 二つのKeyValuePair<string, int>を比較するためのメソッド
static int CompareKeyValuePair(KeyValuePair<string, int> x, KeyValuePair<string, int> y)
{
// Keyで比較した結果を返す
return string.Compare(x.Key, y.Key);
}
static void Main()
{
// ソート対象のDictionary<string, int>
var dict = new Dictionary<string, int>();
dict.Add("Bob", 3);
dict.Add("Dave", 1);
dict.Add("Alice", 2);
dict.Add("Charlie", 5);
dict.Add("Eve", 4);
// Dictionaryの内容をコピーして、List<KeyValuePair<string, int>>に変換
var pairs = new List<KeyValuePair<string, int>>(dict);
// List.Sortメソッドを使ってソート
// (引数に比較方法を定義したメソッドを指定する)
pairs.Sort(CompareKeyValuePair);
foreach (var pair in pairs) {
Console.WriteLine("{0} {1}", pair.Key, pair.Value);
}
}
}
Imports System
Imports System.Collections.Generic
Class Sample
' 二つのKeyValuePair(Of String, Integer)を比較するためのメソッド
Shared Function CompareKeyValuePair(ByVal x As KeyValuePair(Of String, Integer), _
ByVal y As KeyValuePair(Of String, Integer)) As Integer
' Keyで比較した結果を返す
Return String.Compare(x.Key, y.Key)
End Function
Shared Sub Main()
' ソート対象のDictionary
Dim dict As New Dictionary(Of String, Integer)()
dict.Add("Bob", 3)
dict.Add("Dave", 1)
dict.Add("Alice", 2)
dict.Add("Charlie", 5)
dict.Add("Eve", 4)
' Dictionaryの内容をコピーして、List(Of KeyValuePair(Of String, Integer))に変換
Dim pairs As New List(Of KeyValuePair(Of String, Integer))(dict)
' List.Sortメソッドを使ってソート
' (引数に比較方法を定義したメソッドを指定する)
pairs.Sort(AddressOf CompareKeyValuePair)
For Each pair As KeyValuePair(Of String, Integer) In pairs
Console.WriteLine("{0} {1}", pair.Key, pair.Value)
Next
End Sub
End Class
Alice 2 Bob 3 Charlie 5 Dave 1 Eve 4
List.Sortメソッドは、CompareKeyValuePairメソッドで定義されている比較処理にしたがってソートを行います。 上記の例ではキーを比較したため、Dictionaryはキーを基準にソートされました。 比較方法の定義を変えればソートの順序を変更することもできます。 例えば、CompareKeyValuePairを次のように変更することにより、Dictionaryを値でソートできるようになります。
// 二つのKeyValuePair<string, int>を比較するためのメソッド
static int CompareKeyValuePair(KeyValuePair<string, int> x, KeyValuePair<string, int> y)
{
// Valueで比較した結果を返す
return x.Value.CompareTo(y.Value);
// 単に次のようにしても同じ
// return x.Value - y.Value;
}
' 二つのKeyValuePair(Of String, Integer)を比較するためのメソッド
Shared Function CompareKeyValuePair(ByVal x As KeyValuePair(Of String, Integer), _
ByVal y As KeyValuePair(Of String, Integer)) As Integer
' Valueで比較した結果を返す
Return x.Value.CompareTo(b.Value)
' 単に次のようにしても同じ
' Return y.Value - b.Value
End Function
Dave 1 Alice 2 Bob 3 Eve 4 Charlie 5
List.Sortメソッドと比較方法の定義(Comparison<T>デリゲート)については、複合型のソート・複数キーでのソートで詳しく解説します。
キーと値の配列に変換してソートする
2つ目は、Dictionaryの内容を、キーと値で個別の配列に変えてからソートする方法です。
Dictionary<string, int> | |
"Dave" | 1 |
"Alice" | 2 |
"Bob" | 3 |
"Eve" | 4 |
"Charlie" | 5 |
→ 変換 →
string[] | ⇔ | int[] |
"Dave" | ⇔ | 1 |
"Alice" | ⇔ | 2 |
"Bob" | ⇔ | 3 |
"Eve" | ⇔ | 4 |
"Charlie" | ⇔ | 5 |
→ ソート →
string[] | ⇔ | int[] |
"Alice" | ⇔ | 2 |
"Bob" | ⇔ | 3 |
"Charlie" | ⇔ | 5 |
"Dave" | ⇔ | 1 |
"Eve" | ⇔ | 4 |
Array.Sortメソッドには、キーと値のそれぞれが格納された二つの配列を渡すと、キーの配列に従って対応する値の配列も同時に並べ替えることができるオーバーロードが用意されています。 これを使うことにより、Dictionaryのキーと値の両方を格納した配列を互いに関連付けた状態のままソートすることが出来ます。 KeyValuePairは使わないため、キーが単純型であればソート方法(比較方法)を定義する必要がありません。
この方法によるソートの具体例は次のようになります。
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// ソート対象のDictionary<string, int>
var dict = new Dictionary<string, int>();
dict.Add("Bob", 3);
dict.Add("Dave", 1);
dict.Add("Alice", 2);
dict.Add("Charlie", 5);
dict.Add("Eve", 4);
// キーと値を格納する配列を作成し、Dictionaryの内容をコピー
var sortedKeys = new string[dict.Count];
var sortedValues = new int[dict.Count];
dict.Keys.CopyTo(sortedKeys, 0);
dict.Values.CopyTo(sortedValues, 0);
// Array.Sort(Array, Array)メソッドを使ってソート
Array.Sort(sortedKeys, sortedValues);
for (var index = 0; index < sortedKeys.Length; index++) {
Console.WriteLine("{0} {1}", sortedKeys[index], sortedValues[index]);
}
}
}
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' ソート対象のDictionary
Dim dict As New Dictionary(Of String, Integer)()
dict.Add("Bob", 3)
dict.Add("Dave", 1)
dict.Add("Alice", 2)
dict.Add("Charlie", 5)
dict.Add("Eve", 4)
' キーと値を格納する配列を作成し、Dictionaryの内容をコピー
Dim sortedKeys(dict.Count - 1) As String
Dim sortedValues(dict.Count - 1) As Integer
dict.Keys.CopyTo(sortedKeys, 0)
dict.Values.CopyTo(sortedValues, 0)
' Array.Sort(Array, Array)メソッドを使ってソート
Array.Sort(sortedKeys, sortedValues)
For index As Integer = 0 To sortedKeys.Length - 1
Console.WriteLine("{0} {1}", sortedKeys(index), sortedValues(index))
Next
End Sub
End Class
Alice 2 Bob 3 Charlie 5 Dave 1 Eve 4
なお、Array.Sortに渡す配列はキーの配列・値の配列の順となっています。 この順序を逆に指定すれば、値でソートできるようになります。
:
:
dict.Keys.CopyTo(sortedKeys, 0);
dict.Values.CopyTo(sortedValues, 0);
// Array.Sort(Array, Array)メソッドを使ってソート
Array.Sort(sortedValues, sortedKeys);
:
:
:
:
dict.Keys.CopyTo(sortedKeys, 0)
dict.Values.CopyTo(sortedValues, 0)
' Array.Sort(Array, Array)メソッドを使ってソート
Array.Sort(sortedValues, sortedKeys)
:
:
Dave 1 Alice 2 Bob 3 Eve 4 Charlie 5
OrderByを使ってソートする
拡張メソッドであるOrderByメソッドを使うことでもDictionaryをソートできます。 OrderByメソッドを使ったDictionaryのソートについては後述します。
Enumerable.OrderBy
IEnumerable<T>インターフェイスを実装しているコレクションの場合、拡張メソッドであるOrderByを使うことによってソートする事ができます。
配列や、ListやDictionaryを含むジェネリックコレクションクラスはいずれもIEnumerable<T>を実装しているため、OrderByメソッドでソートする事ができます。
OrderByメソッドの使い方と動作
OrderByメソッドを使って配列・Listをソートする例について見ていきます。
using System;
using System.Linq;
class Sample {
static void Main()
{
// ソート対象の配列
var arr = new int[] {5, 2, 3, 1, 4};
// ソート
IOrderedEnumerable<int> sorted = arr.OrderBy(val => val);
// ソート後の結果を列挙して表示
foreach (var val in sorted) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
using System;
using System.Collections.Generic;
using System.Linq;
class Sample {
static void Main()
{
// ソート対象のList<int>
List<int> list = new List<int>(new int[] {5, 2, 3, 1, 4});
// ソート
IOrderedEnumerable<int> sorted = list.OrderBy(val => val);
// ソート後の結果を列挙して表示
foreach (int val in sorted) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Linq
Class Sample
Shared Sub Main()
' ソート対象の配列
Dim arr() As Integer = New Integer() {5, 2, 3, 1, 4}
' ソート
Dim sorted As IOrderedEnumerable(Of Integer) = arr.OrderBy(Function(val) val)
' ソート後の結果を列挙して表示
For Each val As Integer In sorted
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Sample
Shared Sub Main()
' ソート対象のList(Of Integer)
Dim list As New List(Of Integer)(New Integer() {5, 2, 3, 1, 4})
' ソート
Dim sorted As IOrderedEnumerable(Of Integer) = list.OrderBy(Function(val) val)
' ソート後の結果を列挙して表示
For Each val As Integer In sorted
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
1, 2, 3, 4, 5,
Array.SortメソッドやList.Sortメソッドとは異なり、OrderByメソッドは元の配列・コレクションの状態を変更しません(非破壊的なソート)。 代わりにソート後の結果となるIOrderedEnumerable<TElement>を返します。
IOrderedEnumerable<TElement>はIEnumerable<T>から派生したインターフェイスで、後述する点を除けば違いを特に意識しなくてもIEnumerable<T>と同様に扱えます。 ほとんどの場合、この戻り値を直接列挙したり、他のコレクションに格納しなおしたりして使用することになります。
IEnumerable<T>についてはIEnumerable・IEnumeratorを参照してください。
OrderByメソッドは遅延実行されるため、戻り値のIOrderedEnumerable<TElement>に対してforeach等による列挙操作を行うことで初めてソートが行われます。 戻り値を即座に列挙したり、他のコレクションに格納する場合は特にこの動作を意識する必要はありませんが、§.元のコレクションに対する変更とOrderByメソッドの結果への影響で解説するように扱い方によっては意図に反する動作となる場合もあるので、遅延実行となることとその動作については把握しておく必要があります。
OrderByメソッドとキーの選択
OrderByメソッドの引数keySelectorには、ソートの際に使用するキーを選択するメソッドへのデリゲート(またはラムダ式)を指定します。 先の例ではラムダ式を用いていましたが、これをメソッドとして展開すると次のようになります。
using System;
using System.Linq;
class Sample {
// ソートの際に使用するキーを選択するメソッド
static int KeySelector(int val)
{
// 要素の値そのものをソートの際のキーとする
return val;
}
static void Main()
{
// ソート対象の配列
var arr = new int[] {5, 2, 3, 1, 4};
// ソート
IOrderedEnumerable<int> sorted = arr.OrderBy(KeySelector);
foreach (var val in sorted) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Linq
Class Sample
' ソートの際に使用するキーを選択するメソッド
Shared Function KeySelector(ByVal val As Integer) As Integer
' 要素の値そのものをソートの際のキーとする
Return val
End Function
Shared Sub Main()
' ソート対象の配列
Dim arr() As Integer = New Integer() {5, 2, 3, 1, 4}
' ソート
Dim sorted As IOrderedEnumerable(Of Integer) = arr.OrderBy(AddressOf KeySelector)
For Each val As Integer In sorted
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
OrderByメソッドの引数keySelectorとキー選択のメソッドについて詳しく見ていきます。
OrderByメソッドでは、ソートの際に何をキーとしてソートするかを引数keySelectorとして指定する必要があります。 これは、単純型でも複合型でもソートできるようにするために必要となるものです。 数値や文字列など単純型の配列・コレクションの場合は、単に要素そのもの(つまり数値の値や文字列自体)をキーとすればよいため、上記の例のように一見するとあまり意味のない記述となります。 しかし、Dictionaryや複合型の配列・コレクションの場合は、何を基準にソートするかによってキーを定める必要があるため、この引数が意味を持つようになります。
例として、文字列型のNameというプロパティを持つAccountクラスをソートしたい場合は、次のようにキー選択のメソッドを定義する必要があります。 この例を見れば、keySelectorの持つ意味が理解しやすくなると思います。
// Accountクラスのソートの際に使用するキーを選択するメソッド
static string KeySelector(Account val)
{
// Account.Nameプロパティの値をソートの際のキーとする
return val.Name;
}
' Accountクラスのソートの際に使用するキーを選択するメソッド
Shared Function KeySelector(ByVal val As Account) As String
' Account.Nameプロパティの値をソートの際のキーとする
Return val.Name
End Function
比較のために、先の例におけるキー選択のメソッドを抜粋します。 このメソッドでは、int/Integer型のソートをするために、そのキーとしてint/Integerの持つ値を選択しています。
static int KeySelector(int val)
{
return val;
}
Shared Function KeySelector(ByVal val As Integer) As Integer
Return val
End Function
このように、keySelectorには引数にソート対象をとり、戻り値としてソート対象のキーを返すメソッド(またラムダ式)を指定します。
OrderByメソッドを使ったDictionaryのソート
OrderByメソッドを使った具体的な例として、Dictionaryのソートを行う例について見てみます。
次の例のメソッドKeySelectorはキーの選択を行うメソッドです。 Dictionaryの場合は個々の要素がKeyValuePairとして格納されているため、KeyValuePairの何をキーとするかを定める必要があります。 Dictionaryをキーでソートするためには、KeyValuePair.Keyプロパティを並べ替えの際のキーとするようにします。 KeySelectorメソッドでは、このようなキー選択の動作を定義しています。 OrderByメソッドの引数にKeySelectorメソッドを渡すことにより、その定義にしたがってソートが行われます。
using System;
using System.Collections.Generic;
using System.Linq;
class Sample {
static string KeySelector(KeyValuePair<string, int> pair)
{
// 並べ替えの際のキーにKeyの値を使用する
return pair.Key;
}
static void Main()
{
// ソート対象のDictionary<string, int>
var dict = new Dictionary<string, int>();
dict.Add("Bob", 3);
dict.Add("Dave", 1);
dict.Add("Alice", 2);
dict.Add("Charlie", 5);
dict.Add("Eve", 4);
// ソート
IOrderedEnumerable<KeyValuePair<string, int>> sorted = dict.OrderBy(KeySelector);
foreach (var pair in sorted) {
Console.WriteLine("{0} {1}", pair.Key, pair.Value);
}
}
}
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Sample
Shared Function KeySelector(ByVal pair As KeyValuePair(Of String, Integer)) As String
' 並べ替えの際のキーにKeyの値を使用する
Return pair.Key
End Function
Shared Sub Main()
' ソート対象のDictionary
Dim dict As New Dictionary(Of String, Integer)()
dict.Add("Bob", 3)
dict.Add("Dave", 1)
dict.Add("Alice", 2)
dict.Add("Charlie", 5)
dict.Add("Eve", 4)
' ソート
Dim sorted As IOrderedEnumerable(Of KeyValuePair(Of String, Integer)) = dict.OrderBy(AddressOf KeySelector)
For Each pair As KeyValuePair(Of String, Integer) In sorted
Console.WriteLine("{0} {1}", pair.Key, pair.Value)
Next
End Sub
End Class
Alice 2 Bob 3 Charlie 5 Dave 1 Eve 4
上記の例ではDictionaryをキーにしたがってソートするためにKeyValuePair.Keyをキーとしていました。 一方、Dictionaryを値にしたがってソートしたい場合は、次のようにKeyValuePair.ValueをキーとするようにKeySelectorを変えるだけで出来ます(キーの型に合わせてメソッドの戻り値を変えている点に注意してください)。
static int KeySelector(KeyValuePair<string, int> pair)
{
// 並べ替えの際のキーにValueの値を使用する
return pair.Value;
}
Shared Function KeySelector(ByVal pair As KeyValuePair(Of String, Integer)) As Integer
' 並べ替えの際のキーにValueの値を使用する
Return pair.Value
End Function
比較のために、先の例をラムダ式を使ったものに書き換えると次のようになります。 OrderByメソッドで指定しているラムダ式は、上記の例におけるKeySelectorメソッドと同じ動作をします。 ラムダ式を使用すると、キーを選択するコードを個別のメソッドとして記述する必要がなくなるため、よりシンプルに記述できます。
using System;
using System.Collections.Generic;
using System.Linq;
class Sample {
static void Main()
{
// ソート対象のDictionary<string, int>
var dict = new Dictionary<string, int>();
dict.Add("Bob", 3);
dict.Add("Dave", 1);
dict.Add("Alice", 2);
dict.Add("Charlie", 5);
dict.Add("Eve", 4);
// ソート
IOrderedEnumerable<KeyValuePair<string, int>> sorted = dict.OrderBy(pair => pair.Key);
foreach (var pair in sorted) {
Console.WriteLine("{0} {1}", pair.Key, pair.Value);
}
}
}
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Sample
Shared Sub Main()
' ソート対象のDictionary
Dim dict As New Dictionary(Of String, Integer)()
dict.Add("Bob", 3)
dict.Add("Dave", 1)
dict.Add("Alice", 2)
dict.Add("Charlie", 5)
dict.Add("Eve", 4)
' ソート
Dim sorted As IOrderedEnumerable(Of KeyValuePair(Of String, Integer)) = _
dict.OrderBy(Function(pair) pair.Key)
For Each pair As KeyValuePair(Of String, Integer) In sorted
Console.WriteLine("{0} {1}", pair.Key, pair.Value)
Next
End Sub
End Class
Dictionaryを値にしたがってソートしたい場合は、キー選択のラムダ式を次のように変更します。
dict.OrderBy(pair => pair.Value);
dict.OrderBy(Function(pair) pair.Value)
OrderByメソッドの代わりにOrderByDescendingメソッドを使うと、昇順ではなく降順でソートすることができます。
元のコレクションに対する変更とOrderByメソッドの結果への影響
OrderByメソッドは遅延実行されるため、メソッドを呼び出した時点では結果は確定していません。 OrderByメソッドの戻り値を列挙する(もしくは配列・リストに変換する)時点ではじめて結果が確定します。
そのため、次の例のように、OrderByメソッドを呼び出してその結果が確定する前に元のコレクションに変更を加えると、その変更はソート後の結果にも影響するという点に注意が必要です。
using System;
using System.Collections.Generic;
using System.Linq;
class Sample {
static void Main()
{
var list = new List<int>(new int[] {
3, 1, 2,
});
// ソート(この時点では結果が確定していない点に注意)
IOrderedEnumerable<int> sorted = list.OrderBy(val => val);
// 元になったリストに変更を加える
list.Add(5);
list.Add(4);
// 列挙して結果を表示
foreach (var val in sorted) {
Console.Write("{0} ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Sample
Shared Sub Main()
Dim list As New List(Of Integer)(New Integer() { _
3, 1, 2 _
})
' ソート(この時点では結果が確定していない点に注意)
Dim sorted As IOrderedEnumerable(Of Integer) = list.OrderBy(Function(val) val)
' 元になったリストに変更を加える
list.Add(5)
list.Add(4)
' 列挙して結果を表示
For Each val As Integer In sorted
Console.Write("{0} ", val)
Next
Console.WriteLine()
End Sub
End Class
1 2 3 4 5
上記のように、列挙する時点でソートが行われるため、OrderByを呼び出した後に追加した要素もソートされた上で列挙されます。
降順でのソート
ここでは降順(大きい順)でのソートについて、いくつかの方法を見ていきます。
Sort + Reverse
1つ目は、Sortメソッドで昇順にソートしてから、Reverseメソッドで逆順(つまり降順)にするものです。 配列・ArrayList・List<T>にはそれぞれArray.Reverse, ArrayList.Reverse, List.Reverseの各メソッドが用意されていて、これを使うことで要素を逆順に並び替える事が出来ます。
using System;
class Sample {
static void Main()
{
// ソート対象の配列
var arr = new int[] {5, 2, 3, 1, 4};
// ソート
Array.Sort(arr);
// リバース
Array.Reverse(arr);
foreach (var val in arr) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
using System;
using System.Collections.Generic;
class Sample {
static void Main()
{
// ソート対象のList<int>
List<int> list = new List<int>(new int[] {5, 2, 3, 1, 4});
// ソート
list.Sort();
// リバース
list.Reverse();
foreach (int val in list) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Class Sample
Shared Sub Main()
' ソート対象の配列
Dim arr() As Integer = New Integer() {5, 2, 3, 1, 4}
' ソート
Array.Sort(arr)
' リバース
Array.Reverse(arr)
For Each val As Integer In arr
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
Imports System
Imports System.Collections.Generic
Class Sample
Shared Sub Main()
' ソート対象のList(Of Integer)
Dim list As New List(Of Integer)(New Integer() {5, 2, 3, 1, 4})
' ソート
list.Sort()
' リバース
list.Reverse()
For Each val As Integer In list
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
5, 4, 3, 2, 1,
Reverseメソッドそのものは単に要素を逆順に並び替えるだけなので、Reverseメソッドだけを呼び出しても降順には並び替えられません。 必ずSortメソッドで昇順にソートしてから呼び出す必要があります。
Reverseメソッドは、Array.SortやList.Sortメソッドと同様、元になった配列・コレクション自体の内容を逆順にします(破壊的変更)。 非破壊的な方法で降順にソートしたい(元の配列・コレクションは維持したままにしたい)場合は、OrderByDescendingメソッドを使用することができます。
Sort + Comparison<T>
2つ目は、SortメソッドとComparison<T>デリゲートを組み合わせる方法です。 Sortメソッドに特に引数を指定しない場合、Sortメソッドはデフォルト(つまり昇順)の並び替え順序でソートします。 Sortメソッドの引数に並び替え順序を定義したメソッドを表すComparison<T>デリゲートを指定すると、その順序に従ってソートするようになります。
したがって、降順に並び替えるよう動作を定義するメソッドを用意してそれをSortメソッドに渡すことにより、降順にソートする事ができます。 なお、この方法はComparison<T>デリゲートを引数にとることが出来るArray.SortメソッドとList.Sortメソッドで使うことが出来ます。 (ArrayList.SortメソッドではIComparerを指定する必要があります)
using System;
using System.Collections.Generic;
class Sample {
// 二つのintを比較するためのメソッド
static int CompareDescending(int x, int y)
{
return y.CompareTo(x);
// 単に次のようにしても同じ結果となる
// return y - x;
// return -x.CompareTo(y);
// 参考までに、昇順の場合は次のように記述する
// return x.CompareTo(y);
// return x - y;
}
static void Main()
{
// ソート対象のList<int>
var list = new List<int>(new int[] {5, 2, 3, 1, 4});
// ソート
list.Sort(CompareDescending);
foreach (var val in list) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections.Generic
Class Sample
' 二つのIntegerを比較するためのメソッド
Shared Function CompareDescending(ByVal x As Integer, ByVal y As Integer) As Integer
Return y.CompareTo(x)
' 単に次のようにしても同じ結果となる
' Return y - x
' Return -x.CompareTo(y)
' 参考までに、昇順の場合は次のように記述する
' Return x.CompareTo(y)
' Return x - y
End Function
Shared Sub Main()
' ソート対象のList(Of Integer)
Dim list As New List(Of Integer)(New Integer() {5, 2, 3, 1, 4})
' ソート
list.Sort(AddressOf CompareDescending)
' 降順にソートして表示
For Each val As Integer In list
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
5, 4, 3, 2, 1,
SortメソッドとComparison<T>デリゲートについては、複合型のソート・複数キーでのソートでも改めて解説します。
Sortメソッドと型ごとのデフォルトのソート順については基本型とデフォルトのソート順で解説しています。
OrderByDescending
3つ目は、拡張メソッドであるOrderByDescendingメソッドを使う方法です。 既に解説したOrderByメソッドは配列・コレクションを昇順にソートするものでしたが、OrderByDescendingメソッドは降順にソートするものです。
using System;
using System.Linq;
class Sample {
static void Main()
{
// ソート対象の配列
var arr = new int[] {5, 2, 3, 1, 4};
// 降順にソートして表示
foreach (var val in arr.OrderByDescending(val => val)) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
using System;
using System.Collections.Generic;
using System.Linq;
class Sample {
static void Main()
{
// ソート対象のList<int>
List<int> list = new List<int>(new int[] {5, 2, 3, 1, 4});
// 降順にソートして表示
foreach (int val in list.OrderByDescending(val => val)) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Linq
Class Sample
Shared Sub Main()
' ソート対象の配列
Dim arr() As Integer = New Integer() {5, 2, 3, 1, 4}
' 降順にソートして表示
For Each val As Integer In arr.OrderByDescending(Function(e) e)
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Sample
Shared Sub Main()
' ソート対象のList(Of Integer)
Dim list As New List(Of Integer)(New Integer() {5, 2, 3, 1, 4})
' 降順にソートして表示
For Each val As Integer In list.OrderByDescending(Function(e) e)
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
5, 4, 3, 2, 1,
降順にソートされる点を除けばOrderByDescendingメソッドはOrderByメソッドと同じなので、引数や動作について詳しくはOrderByメソッドについての解説を参照してください。
シャッフル
ここまでは規則性のある順序でのソートを行ってきましたが、この順序をランダムにすることで配列やListをシャッフルすることが出来ます。 OrderByメソッドの場合、与えられたキーに基づいて並べ替えが行われますが、このキーにランダムな値を与えることでコレクションをシャッフルすることが出来ます。 次の例ではOrderByメソッドを使ってListをシャッフルしています。
using System;
using System.Collections.Generic;
using System.Linq;
class Sample {
static Random rand = new Random();
static int RandomKeySelector(int val)
{
// valに関係なく、ランダムなキーを返す
return rand.Next();
}
static void Main()
{
var list = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
foreach (var val in list.OrderBy(RandomKeySelector)) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections.Generic
Imports System.Linq
Class Sample
Shared rand As Random = New Random()
Shared Function RandomKeySelector(ByVal val As Integer) As Integer
' valに関係なく、ランダムなキーを返す
Return rand.Next()
End Function
Shared Sub Main()
Dim list As New List(Of Integer)(New Integer() {0, 1, 2, 3, 4, 5, 6, 7, 8, 9})
' シャッフル
For Each val As Integer In list.OrderBy(AddressOf RandomKeySelector)
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
9, 0, 6, 3, 4, 5, 8, 1, 7, 2,
一方、Array.Sortメソッドではこのような方法は使えません。 次の例では、Array.Sortメソッドに毎回異なる結果を返すIComparer<T>を指定することで配列をシャッフルしようとしています。 IComparer<T>は、Comparison<T>デリゲートと同様の大小関係を定義するメソッドをクラスに実装するためのインターフェイスです。 大小関係をランダムにすることで一見シャッフル出来るように思えますが、実際にArray.Sortメソッドを呼び出すと、場合によっては大小関係に矛盾が生じて例外がスローされるため、期待通りには動作しません。
using System;
using System.Collections.Generic;
class Sample {
// ランダムに並べ替えるためのIComparer<int>を実装するクラス
class RandomComparer : IComparer<int> {
public int Compare(int x, int y)
{
// -1, 0, +1いずれかの値をランダムに返す
return rand.Next(-1, 2);
}
private Random rand = new Random();
}
static void Main()
{
var arr = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// シャッフル
Array.Sort(arr, new RandomComparer());
foreach (var val in arr) {
Console.Write("{0}, ", val);
}
Console.WriteLine();
}
}
Imports System
Imports System.Collections.Generic
Class Sample
' ランダムに並べ替えるためのIComparer(Of Integer)を実装するクラス
Class RandomComparer
Implements IComparer(Of Integer)
Public Function Compare(ByVal x As Integer, ByVal y As Integer) As Integer Implements IComparer(Of Integer).Compare
' -1, 0, +1いずれかの値をランダムに返す
Return rand.Next(-1, 2)
End Function
Private rand As Random = New Random()
End Class
Shared Sub Main()
Dim arr As Integer() = New Integer() {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
' シャッフル
Array.Sort(arr, New RandomComparer())
For Each val As Integer In arr
Console.Write("{0}, ", val)
Next
Console.WriteLine()
End Sub
End Class
7, 8, 9, 4, 3, 1, 0, 2, 5, 6,
ハンドルされていない例外: System.ArgumentException: IComparer.Compare() メソッドから矛盾する結果が返されたため、並べ替えできません。値をそれ自体と比較したときに等しい結果にならないか、またはある値を別の値と繰り返し比較したときに異なる結果が生じます。x: '0'、x の型: 'Int32'、IComparer: ''。 場所 System.Collections.Generic.GenericArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) 場所 System.Array.Sort[T](T[] array, Int32 index, Int32 length, IComparer`1 comparer) 場所 System.Array.Sort[T](T[] array, IComparer`1 comparer) 場所 Sample.Main()
その他のシャッフルの実装例については配列・コレクションのシャッフル、より適切な乱数の取得方法については乱数、IComparer<T>については大小関係の定義と比較を参照してください。
パフォーマンスの比較
ここではソートを行ういくつかのケースについてパフォーマンスの比較を行った結果を紹介します。 比較メソッドの定義方法やソートするデータの種類等によっては結果が変わるので、ここで紹介している結果はあくまで参考程度のものです。
Sort vs OrderBy
SortメソッドとOrderByメソッドを比較すると、OrderByメソッドでは各要素の比較の度にキーの選択が行われる分だけ速度の面で劣るようです。 以下のコードでは、それぞれ100個、10,000個、1,000,000個の要素を持つList<int>に対してSortメソッドとOrderByメソッドでソートし、列挙する操作をそれぞれ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++) {
TestSort(CreateSource(count, i));
TestOrderBy(CreateSource(count, i));
}
}
}
static List<int> CreateSource(int count, int seed)
{
var rand = new Random(seed);
var list = new List<int>();
for (var i = 0; i < count; i++) {
list.Add(rand.Next());
}
return list;
}
static void TestSort(List<int> source)
{
var sw = Stopwatch.StartNew();
source.Sort();
foreach (var val in source) {
}
sw.Stop();
Console.WriteLine(" Sort : {0}", sw.Elapsed);
}
static void TestOrderBy(List<int> source)
{
var sw = Stopwatch.StartNew();
foreach (var val in source.OrderBy(val => val)) {
}
sw.Stop();
Console.WriteLine(" OrderBy: {0}", sw.Elapsed);
}
}
Microsoft Windows NT 6.1.7601 Service Pack 1 4.0.30319.239 100 Sort : 00:00:00.0001313 OrderBy: 00:00:00.0149608 Sort : 00:00:00.0000150 OrderBy: 00:00:00.0000787 Sort : 00:00:00.0000159 OrderBy: 00:00:00.0000382 10,000 Sort : 00:00:00.0009744 OrderBy: 00:00:00.0037582 Sort : 00:00:00.0010783 OrderBy: 00:00:00.0038236 Sort : 00:00:00.0009956 OrderBy: 00:00:00.0041097 1,000,000 Sort : 00:00:00.1425273 OrderBy: 00:00:01.1132711 Sort : 00:00:00.1422619 OrderBy: 00:00:01.1064369 Sort : 00:00:00.1396308 OrderBy: 00:00:01.1138493
Unix 3.0.0.14 4.0.30319.1 100 Sort : 00:00:00.0043755 OrderBy: 00:00:00.0147171 Sort : 00:00:00.0000182 OrderBy: 00:00:00.0000361 Sort : 00:00:00.0000169 OrderBy: 00:00:00.0000277 10,000 Sort : 00:00:00.0024438 OrderBy: 00:00:00.0059536 Sort : 00:00:00.0037272 OrderBy: 00:00:00.0054564 Sort : 00:00:00.0024618 OrderBy: 00:00:00.0056411 1,000,000 Sort : 00:00:00.3313208 OrderBy: 00:00:01.0688121 Sort : 00:00:00.3300875 OrderBy: 00:00:01.0192792 Sort : 00:00:00.3305355 OrderBy: 00:00:01.0644162
複数のキーでソートした場合の結果については、複合型のソート・複数キーでのソート §.パフォーマンスの比較を参照してください。
Sort+Reverse vs Sort(Comparison<T>) vs OrderByDescending
降順でソートするために、次の三つの方法をとり、それぞれの速度を比較してみます。
- SortメソッドとReverseメソッドを組み合わせる場合
- 降順にソートするComparison<T>を指定してSortメソッドを呼び出す場合
- OrderByDescendingメソッドを用いる場合
以下のコードでは、それぞれ100個、10,000個、1,000,000個の要素を持つList<int>に対して降順でのソート・列挙の操作をそれぞれ3回試行した場合の経過時間を比較しています。 実装系で結果に違いはあるものの、速度の点ではSort+ReverseおよびSort(Comparison<T>)で大きな差はなく、OrderByDescendingは他と比べるとやや劣るようです。
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++) {
TestSortReverse(CreateSource(count, i));
TestSortComparison(CreateSource(count, i));
TestOrderByDescending(CreateSource(count, i));
}
}
}
static List<int> CreateSource(int count, int seed)
{
var rand = new Random(seed);
var list = new List<int>();
for (var i = 0; i < count; i++) {
list.Add(rand.Next());
}
return list;
}
static void TestSortReverse(List<int> source)
{
var sw = Stopwatch.StartNew();
source.Sort();
source.Reverse();
foreach (var val in source) {
}
sw.Stop();
Console.WriteLine(" Sort + Reverse : {0}", sw.Elapsed);
}
static void TestSortComparison(List<int> source)
{
var sw = Stopwatch.StartNew();
source.Sort((x, y) => y - x);
foreach (var val in source) {
}
sw.Stop();
Console.WriteLine(" Sort(Comparison<T>): {0}", sw.Elapsed);
}
static void TestOrderByDescending(List<int> source)
{
var sw = Stopwatch.StartNew();
foreach (var val in source.OrderByDescending(val => val)) {
}
sw.Stop();
Console.WriteLine(" OrderByDescending : {0}", sw.Elapsed);
}
}
Microsoft Windows NT 6.1.7601 Service Pack 1 4.0.30319.239 100 Sort + Reverse : 00:00:00.0001307 Sort(Comparison<T>): 00:00:00.0006023 OrderByDescending : 00:00:00.0216231 Sort + Reverse : 00:00:00.0000164 Sort(Comparison<T>): 00:00:00.0000399 OrderByDescending : 00:00:00.0000463 Sort + Reverse : 00:00:00.0000100 Sort(Comparison<T>): 00:00:00.0000189 OrderByDescending : 00:00:00.0000268 10,000 Sort + Reverse : 00:00:00.0015731 Sort(Comparison<T>): 00:00:00.0023103 OrderByDescending : 00:00:00.0048779 Sort + Reverse : 00:00:00.0010660 Sort(Comparison<T>): 00:00:00.0025257 OrderByDescending : 00:00:00.0045271 Sort + Reverse : 00:00:00.0009719 Sort(Comparison<T>): 00:00:00.0020695 OrderByDescending : 00:00:00.0047003 1,000,000 Sort + Reverse : 00:00:00.1403080 Sort(Comparison<T>): 00:00:00.3427332 OrderByDescending : 00:00:01.0785580 Sort + Reverse : 00:00:00.1400711 Sort(Comparison<T>): 00:00:00.3498478 OrderByDescending : 00:00:01.0661894 Sort + Reverse : 00:00:00.1424873 Sort(Comparison<T>): 00:00:00.3463507 OrderByDescending : 00:00:01.0516224
Unix 3.0.0.14 4.0.30319.1 100 Sort + Reverse : 00:00:00.0047614 Sort(Comparison<T>): 00:00:00.0006060 OrderByDescending : 00:00:00.0156435 Sort + Reverse : 00:00:00.0000188 Sort(Comparison<T>): 00:00:00.0000161 OrderByDescending : 00:00:00.0000431 Sort + Reverse : 00:00:00.0000171 Sort(Comparison<T>): 00:00:00.0000155 OrderByDescending : 00:00:00.0000287 10,000 Sort + Reverse : 00:00:00.0025755 Sort(Comparison<T>): 00:00:00.0025991 OrderByDescending : 00:00:00.0055562 Sort + Reverse : 00:00:00.0024163 Sort(Comparison<T>): 00:00:00.0032577 OrderByDescending : 00:00:00.0057701 Sort + Reverse : 00:00:00.0027872 Sort(Comparison<T>): 00:00:00.0025708 OrderByDescending : 00:00:00.0065627 1,000,000 Sort + Reverse : 00:00:00.3615682 Sort(Comparison<T>): 00:00:00.3654408 OrderByDescending : 00:00:00.9620297 Sort + Reverse : 00:00:00.3455927 Sort(Comparison<T>): 00:00:00.3638741 OrderByDescending : 00:00:00.9560158 Sort + Reverse : 00:00:00.3475420 Sort(Comparison<T>): 00:00:00.3706791 OrderByDescending : 00:00:00.9840878