ここでは、配列・List・Dictionaryなどの各種コレクションを使ったデータの並べ替え、ソート(sort)について解説します。 ソートするにはどのようにすればよいかを主眼に置くため、ここでは数値型や文字列型などの単純型(基本型)からなるコレクションのソートのみを扱います。 ソートしたい対象が決まっていて、そのソート方法を知りたい場合は以下の項を参照してください。
- 配列をソートしたい
- →§.配列のソート (Array.Sort)
- Listをソートしたい
- →§.Listのソート (List.Sort)
- Dictionaryをソートしたい
- →§.Dictionaryのソート
- 降順でソートしたい
ソート順を逆にしたい - →§.降順でのソート
上記のようなソートのメソッドについては既に知っていて、その上でソートの動作を詳細にカスタマイズしたり、基本型以外の型をソートしたいといった場合には、ソート対象やソートの目的に応じて以下の文章を参照してください。
ソート
ここでは、配列・List・Dictionaryなどを使ったデータの並べ替えについて見ていきます。 まずは昇順(小さい順)でソートする方法について解説します。 降順(大きい順)でのソート方法については追って解説します。
配列のソート (Array.Sort)
配列をソートするには、Array.Sortメソッドを使います。 このメソッドは静的メソッドで、引数に指定された配列をソートします。
Array.Sortメソッドでは、引数に指定された配列自体をソートします(破壊的変更)。 ソートされた配列が新たに作成され戻り値として返されることはありません。 そのため、ソート前の状態も維持しておきたい場合は、Array.Cloneメソッドなどを使ってあらかじめ配列の複製を作っておき、その後で変更用の配列をソートする必要があります。
非破壊的なソートを行いたい場合はEnumerable.OrderByメソッドを使うことができます。
特に順序を指定しない限り、Array.Sortメソッドはデフォルトのソート順でソートします。 デフォルトのソート順については基本型とデフォルトのソート順、ソート順の定義については大小関係の定義と比較で解説しています。 逆順でのソートについては§.降順でのソートで後述しています。
ジャグ配列・多次元配列のソートについてはジャグ配列・多次元配列のソートで解説します。
独自に定義した型は通常そのままではソートできません。 この場合、ソートができないことを表す例外InvalidOperationExceptionがスローされます。
これはソート対象の大小関係が定義されていないために発生します。 ソートを行うためにはソート対象の大小関係が比較できなければなりませんが、上記の例ではAccountクラスの大小関係がどこにも定義されておらず比較ができないため、ソートの際に例外が発生しています。
Array.Sortメソッドでソートを行うには、ソート対象の型にIComparable<T>(またはIComparable)インターフェイスを実装するか、あるいはSortメソッドの引数にIComparer<T>(またはIComparer)インターフェイス、もしくはComparison<T>デリゲートを指定する必要があります。
詳しくは複合型のソート・複数キーでのソートを参照してください。 また個々のインターフェイスとその実装方法については大小関係の定義と比較を参照してください。
Listのソート (List.Sort)
List<T>をソートするには、List.Sortメソッドを使います。 List.Sortメソッドはメソッドを呼び出したインスタンス自身をソートします。
List.Sortメソッドでは、インスタンス自身をソートします(破壊的変更)。 ソートされたListが新たに作成され戻り値として返されることはありません。 そのため、ソート前の状態も維持しておきたい場合は、あらかじめListの複製を作っておき(ジェネリックコレクション(1) List §.Listの複製)、その後で変更用のListをソートする必要があります。
非破壊的なソートを行いたい場合はEnumerable.OrderByメソッドを使うことができます。
特に順序を指定しない限り、List.Sortメソッドはデフォルトのソート順でソートします。 デフォルトのソート順については基本型とデフォルトのソート順、ソート順の定義については大小関係の定義と比較で解説しています。 逆順でのソートについては§.降順でのソートで後述しています。
独自に定義した型は通常そのままではソートできません。 この場合、ソートができないことを表す例外InvalidOperationExceptionがスローされます。
これはソート対象の大小関係が定義されていないために発生します。 ソートを行うためにはソート対象の大小関係が比較できなければなりませんが、上記の例ではAccountクラスの大小関係がどこにも定義されておらず比較ができないため、ソートの際に例外が発生しています。
List.Sortメソッドでソートを行うには、ソート対象の型にIComparable<T>(またはIComparable)インターフェイスを実装するか、あるいはSortメソッドの引数にIComparer<T>(またはIComparer)インターフェイス、もしくはComparison<T>デリゲートを指定する必要があります。
詳しくは複合型のソート・複数キーでのソートを参照してください。 また個々のインターフェイスとその実装方法については大小関係の定義と比較を参照してください。
ArrayListのソート (ArrayList.Sort)
ArrayListをソートするには、ArrayList.Sortメソッドを使います。 使い方・動作と結果はList<T>.Sortと同様です。
ArrayListを使う以外の方法がないなど、特に理由が無い限りはArrayListではなくList等を用いることが推奨されます。
SortedList, SortedDictionaryのソート
SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>では、要素を格納した時点で自動的にソートされるため、明示的にソートを行うメソッドはありません。 SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>では、キー(TKey)の値を基準にソートされます。
以下の例ではSortedListを使用していますが、SortedDictionaryでも結果は同様です。
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のソート方法(比較方法)を定義するメソッドです。
List.Sortメソッドは、CompareKeyValuePairメソッドで定義されている比較処理にしたがってソートを行います。 上記の例ではキーを比較したため、Dictionaryはキーを基準にソートされました。 比較方法の定義を変えればソートの順序を変更することもできます。 例えば、CompareKeyValuePairを次のように変更することにより、Dictionaryを値でソートできるようになります。
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は使わないため、キーが単純型であればソート方法(比較方法)を定義する必要がありません。
この方法によるソートの具体例は次のようになります。
なお、Array.Sortに渡す配列はキーの配列・値の配列の順となっています。 この順序を逆に指定すれば、値でソートできるようになります。
OrderByを使ってソートする
拡張メソッドであるOrderByメソッドを使うことでもDictionaryをソートできます。 OrderByメソッドを使ったDictionaryのソートについては後述します。
Enumerable.OrderBy
IEnumerable<T>インターフェイスを実装しているコレクションの場合、拡張メソッドであるOrderByを使うことによってソートする事ができます。
配列や、ListやDictionaryを含むジェネリックコレクションクラスはいずれもIEnumerable<T>を実装しているため、OrderByメソッドでソートする事ができます。
OrderByメソッドの使い方と動作
OrderByメソッドを使って配列・Listをソートする例について見ていきます。
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には、ソートの際に使用するキーを選択するメソッドへのデリゲート(またはラムダ式)を指定します。 先の例ではラムダ式を用いていましたが、これをメソッドとして展開すると次のようになります。
OrderByメソッドの引数keySelectorとキー選択のメソッドについて詳しく見ていきます。
OrderByメソッドでは、ソートの際に何をキーとしてソートするかを引数keySelectorとして指定する必要があります。 これは、単純型でも複合型でもソートできるようにするために必要となるものです。 数値や文字列など単純型の配列・コレクションの場合は、単に要素そのもの(つまり数値の値や文字列自体)をキーとすればよいため、上記の例のように一見するとあまり意味のない記述となります。 しかし、Dictionaryや複合型の配列・コレクションの場合は、何を基準にソートするかによってキーを定める必要があるため、この引数が意味を持つようになります。
例として、文字列型のNameというプロパティを持つAccountクラスをソートしたい場合は、次のようにキー選択のメソッドを定義する必要があります。 この例を見れば、keySelectorの持つ意味が理解しやすくなると思います。
比較のために、先の例におけるキー選択のメソッドを抜粋します。 このメソッドでは、int/Integer型のソートをするために、そのキーとしてint/Integerの持つ値を選択しています。
このように、keySelectorには引数にソート対象をとり、戻り値としてソート対象のキーを返すメソッド(またラムダ式)を指定します。
OrderByメソッドを使ったDictionaryのソート
OrderByメソッドを使った具体的な例として、Dictionaryのソートを行う例について見てみます。
次の例のメソッドKeySelectorはキーの選択を行うメソッドです。 Dictionaryの場合は個々の要素がKeyValuePairとして格納されているため、KeyValuePairの何をキーとするかを定める必要があります。 Dictionaryをキーでソートするためには、KeyValuePair.Keyプロパティを並べ替えの際のキーとするようにします。 KeySelectorメソッドでは、このようなキー選択の動作を定義しています。 OrderByメソッドの引数にKeySelectorメソッドを渡すことにより、その定義にしたがってソートが行われます。
上記の例ではDictionaryをキーにしたがってソートするためにKeyValuePair.Keyをキーとしていました。 一方、Dictionaryを値にしたがってソートしたい場合は、次のようにKeyValuePair.ValueをキーとするようにKeySelectorを変えるだけで出来ます(キーの型に合わせてメソッドの戻り値を変えている点に注意してください)。
比較のために、先の例をラムダ式を使ったものに書き換えると次のようになります。 OrderByメソッドで指定しているラムダ式は、上記の例におけるKeySelectorメソッドと同じ動作をします。 ラムダ式を使用すると、キーを選択するコードを個別のメソッドとして記述する必要がなくなるため、よりシンプルに記述できます。
Dictionaryを値にしたがってソートしたい場合は、キー選択のラムダ式を次のように変更します。
OrderByメソッドの代わりにOrderByDescendingメソッドを使うと、昇順ではなく降順でソートすることができます。
元のコレクションに対する変更とOrderByメソッドの結果への影響
OrderByメソッドは遅延実行されるため、メソッドを呼び出した時点では結果は確定していません。 OrderByメソッドの戻り値を列挙する(もしくは配列・リストに変換する)時点ではじめて結果が確定します。
そのため、次の例のように、OrderByメソッドを呼び出してその結果が確定する前に元のコレクションに変更を加えると、その変更はソート後の結果にも影響するという点に注意が必要です。
上記のように、列挙する時点でソートが行われるため、OrderByを呼び出した後に追加した要素もソートされた上で列挙されます。
降順でのソート
ここでは降順(大きい順)でのソートについて、いくつかの方法を見ていきます。
Sort + Reverse
1つ目は、Sortメソッドで昇順にソートしてから、Reverseメソッドで逆順(つまり降順)にするものです。 配列・ArrayList・List<T>にはそれぞれArray.Reverse, ArrayList.Reverse, List.Reverseの各メソッドが用意されていて、これを使うことで要素を逆順に並び替える事が出来ます。
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を指定する必要があります)
SortメソッドとComparison<T>デリゲートについては、複合型のソート・複数キーでのソートでも改めて解説します。
Sortメソッドと型ごとのデフォルトのソート順については基本型とデフォルトのソート順で解説しています。
OrderByDescending
3つ目は、拡張メソッドであるOrderByDescendingメソッドを使う方法です。 既に解説したOrderByメソッドは配列・コレクションを昇順にソートするものでしたが、OrderByDescendingメソッドは降順にソートするものです。
降順にソートされる点を除けばOrderByDescendingメソッドはOrderByメソッドと同じなので、引数や動作について詳しくはOrderByメソッドについての解説を参照してください。
シャッフル
ここまでは規則性のある順序でのソートを行ってきましたが、この順序をランダムにすることで配列やListをシャッフルすることが出来ます。 OrderByメソッドの場合、与えられたキーに基づいて並べ替えが行われますが、このキーにランダムな値を与えることでコレクションをシャッフルすることが出来ます。 次の例ではOrderByメソッドを使ってListをシャッフルしています。
一方、Array.Sortメソッドではこのような方法は使えません。 次の例では、Array.Sortメソッドに毎回異なる結果を返すIComparer<T>を指定することで配列をシャッフルしようとしています。 IComparer<T>は、Comparison<T>デリゲートと同様の大小関係を定義するメソッドをクラスに実装するためのインターフェイスです。 大小関係をランダムにすることで一見シャッフル出来るように思えますが、実際にArray.Sortメソッドを呼び出すと、場合によっては大小関係に矛盾が生じて例外がスローされるため、期待通りには動作しません。
その他のシャッフルの実装例については配列・コレクションのシャッフル、より適切な乱数の取得方法については乱数、IComparer<T>については大小関係の定義と比較を参照してください。
パフォーマンスの比較
ここではソートを行ういくつかのケースについてパフォーマンスの比較を行った結果を紹介します。 比較メソッドの定義方法やソートするデータの種類等によっては結果が変わるので、ここで紹介している結果はあくまで参考程度のものです。
Sort vs OrderBy
SortメソッドとOrderByメソッドを比較すると、OrderByメソッドでは各要素の比較の度にキーの選択が行われる分だけ速度の面で劣るようです。 以下のコードでは、それぞれ100個、10,000個、1,000,000個の要素を持つList<int>に対してSortメソッドとOrderByメソッドでソートし、列挙する操作をそれぞれ3回試行した場合の経過時間を比較しています。
複数のキーでソートした場合の結果については、複合型のソート・複数キーでのソート §.パフォーマンスの比較を参照してください。
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は他と比べるとやや劣るようです。