ここでは、配列・List・Dictionaryなどの各種コレクションを使ったデータの並べ替え、ソート(sort)について解説します。 ソートするにはどのようにすればよいかを主眼に置くため、ここでは数値型や文字列型などの単純型(基本型)からなるコレクションのソートのみを扱います。 ソートしたい対象が決まっていて、そのソート方法を知りたい場合は以下の項を参照してください。

配列をソートしたい
§.配列のソート (Array.Sort)
Listをソートしたい
§.Listのソート (List.Sort)
Dictionaryをソートしたい
§.Dictionaryのソート
降順でソートしたい
ソート順を逆にしたい
§.降順でのソート

上記のようなソートのメソッドについては既に知っていて、その上でソートの動作を詳細にカスタマイズしたり、基本型以外の型をソートしたいといった場合には、ソート対象やソートの目的に応じて以下の文章を参照してください。

§1 ソート

ここでは、配列・List・Dictionaryなどを使ったデータの並べ替えについて見ていきます。 まずは昇順(小さい順)でソートする方法について解説します。 降順(大きい順)でのソート方法については追って解説します。

§1.1 配列のソート (Array.Sort)

配列をソートするには、Array.Sortメソッドを使います。 このメソッドは静的メソッドで、引数に指定された配列をソートします。

Array.Sortで数値の配列をソートする
using System;

class Sample {
  static void Main()
  {
    // ソート対象の配列
    int[] arr = new int[] {5, 2, 3, 1, 4};

    // ソート
    Array.Sort(arr);

    // ソート結果を表示
    foreach (int val in arr) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
1, 2, 3, 4, 5, 
Array.Sortで文字列の配列をソートする
using System;

class Sample {
  static void Main()
  {
    // ソート対象の配列
    string[] arr = new string[] {"ab", "abc", "aa", "a", "b", "acb"};

    // ソート
    Array.Sort(arr);

    // ソート結果を表示
    foreach (string val in arr) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
a, aa, ab, abc, acb, b, 

Array.Sortメソッドでは、引数に指定された配列自体をソートします(破壊的変更)。 ソートされた配列が新たに作成され戻り値として返されることはありません。 そのため、ソート前の状態も維持しておきたい場合は、Array.Cloneメソッドなどを使ってあらかじめ配列の複製を作っておき、その後で変更用の配列をソートする必要があります。

非破壊的なソートを行いたい場合はEnumerable.OrderByメソッドを使うことができます。

特に順序を指定しない限り、Array.Sortメソッドはデフォルトのソート順でソートします。 デフォルトのソート順については基本型とデフォルトのソート順、ソート順の定義については大小関係の定義と比較で解説しています。 逆順でのソートについては§.降順でのソートで後述しています。

ジャグ配列・多次元配列のソートについてはジャグ配列・多次元配列のソートで解説します。


独自に定義した型は通常そのままではソートできません。 この場合、ソートができないことを表す例外InvalidOperationExceptionがスローされます。

Array.Sortでソートできない場合
using System;

// 独自に定義した型
class Account {
  public string Name;

  public Account(string name)
  {
    this.Name = name;
  }
}

class Sample {
  static void Main()
  {
    // ソート対象の配列
    Account[] arr = new Account[] {new Account("Bob"), new Account("Alice"), new Account("Charlie")};

    // ソート
    Array.Sort(arr);
  }
}
実行結果
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>デリゲートを指定する必要があります。

詳しくは複合型のソート・複数キーでのソートを参照してください。 また個々のインターフェイスとその実装方法については大小関係の定義と比較を参照してください。

§1.2 Listのソート (List.Sort)

List<T>をソートするには、List.Sortメソッドを使います。 List.Sortメソッドはメソッドを呼び出したインスタンス自身をソートします。

List.Sortで数値をソートする
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();

    // ソート結果を表示
    foreach (int val in list) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
1, 2, 3, 4, 5, 
List.Sortで文字列をソートする
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    // ソート対象のList<string>
    List<string> list = new List<string>(new string[] {"ab", "abc", "aa", "a", "b", "acb"});

    // ソート
    list.Sort();

    // ソート結果を表示
    foreach (string val in list) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
a, aa, ab, abc, acb, b, 

List.Sortメソッドでは、インスタンス自身をソートします(破壊的変更)。 ソートされたListが新たに作成され戻り値として返されることはありません。 そのため、ソート前の状態も維持しておきたい場合は、あらかじめListの複製を作っておき(ジェネリックコレクション(1) List §.Listの複製)、その後で変更用のListをソートする必要があります。

非破壊的なソートを行いたい場合はEnumerable.OrderByメソッドを使うことができます。

特に順序を指定しない限り、List.Sortメソッドはデフォルトのソート順でソートします。 デフォルトのソート順については基本型とデフォルトのソート順、ソート順の定義については大小関係の定義と比較で解説しています。 逆順でのソートについては§.降順でのソートで後述しています。


独自に定義した型は通常そのままではソートできません。 この場合、ソートができないことを表す例外InvalidOperationExceptionがスローされます。

List.Sortでソートできない場合
using System;
using System.Collections.Generic;

// 独自に定義した型
class Account {
  public string Name;

  public Account(string name)
  {
    this.Name = name;
  }
}

class Sample {
  static void Main()
  {
    // ソート対象のList
    List<Account> list = new List<Account>(new Account[] {new Account("Bob"), new Account("Alice"), new Account("Charlie")});

    // ソート
    list.Sort();
  }
}
実行結果
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>デリゲートを指定する必要があります。

詳しくは複合型のソート・複数キーでのソートを参照してください。 また個々のインターフェイスとその実装方法については大小関係の定義と比較を参照してください。

§1.3 ArrayListのソート (ArrayList.Sort)

ArrayListをソートするには、ArrayList.Sortメソッドを使います。 使い方・動作と結果はList<T>.Sortと同様です。

ArrayList.Sortで数値をソートする
using System;
using System.Collections;

class Sample {
  static void Main()
  {
    // ソート対象のArrayList
    ArrayList list = new ArrayList(new int[] {5, 2, 3, 1, 4});

    // ソート
    list.Sort();

    // ソート結果を表示
    foreach (int val in list) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
1, 2, 3, 4, 5, 
ArrayList.Sortで文字列をソートする
using System;
using System.Collections;

class Sample {
  static void Main()
  {
    // ソート対象のArrayList
    ArrayList list = new ArrayList(new string[] {"ab", "abc", "aa", "a", "b", "acb"});

    // ソート
    list.Sort();

    // ソート結果を表示
    foreach (string val in list) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
a, aa, ab, abc, acb, b, 

ArrayListを使う以外の方法がないなど、特に理由が無い限りはArrayListではなくList等を用いることが推奨されます。

§1.4 SortedList, SortedDictionaryのソート

SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>では、要素を格納した時点で自動的にソートされるため、明示的にソートを行うメソッドはありません。 SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>では、キー(TKey)の値を基準にソートされます。

以下の例ではSortedListを使用していますが、SortedDictionaryでも結果は同様です。

数値をキーとしたSortedListのソート
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 (KeyValuePair<int, string> pair in list) {
      Console.WriteLine("{0} {1}", pair.Key, pair.Value);
    }
  }
}
実行結果
1 Dave
2 Alice
3 Bob
4 Eve
5 Charlie
文字列をキーとしたSortedListのソート
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 (KeyValuePair<string, int> pair in list) {
      Console.WriteLine("{0} {1}", pair.Key, pair.Value);
    }
  }
}
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

SortedList<TKey, TValue>およびSortedDictionary<TKey, TValue>で、値(TValue)の値を基準にソートする手段は用意されていないため、独自にソート処理を実装する必要があります。 詳しくはDictionaryのソートの解説を参照してください。

SortedList・SortedDictionaryのその他の機能と動作についてはジェネリックコレクション(3) SortedListとSortedDictionaryで詳しく解説しています。



§1.5 Dictionaryのソート

Dictionary<TKey, TValue>には、SortedListとSortedDictionaryのように自動的に内容をソートする機能や、List.Sortのようにソートを行うメソッドは用意されていません。

ここでは、Dictionaryをソートする方法のいくつかを見ていきます。 Dictionary自体をソートすることは出来ないため、以下の方法はいずれも元のDictionaryの状態は変更せず、Dictionaryの内容を参照してソートされた状態で取得する方法(非破壊的なソート)となります。

常にソートされた状態にしておきたい場合はDictionaryではなくSortedList・SortedDictionaryを使用することが出来ますが、SortedList・SortedDictionaryでは要素の追加の度にソートされることによるオーバーヘッドが生じます。 これによる処理速度の低下を無視できないなどの理由がある場合は、やはりDictionaryを使い、必要になった時点でソートを行うという方法が必要になります。

§1.5.1 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を使ってDictionaryをソートする (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>
    Dictionary<string, int> 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>>に変換
    List<KeyValuePair<string, int>> pairs = new List<KeyValuePair<string, int>>(dict);

    // List.Sortメソッドを使ってソート
    // (引数に比較方法を定義したメソッドを指定する)
    pairs.Sort(CompareKeyValuePair);

    foreach (KeyValuePair<string, int> pair in pairs) {
      Console.WriteLine("{0} {1}", pair.Key, pair.Value);
    }
  }
}
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

List.Sortメソッドは、CompareKeyValuePairメソッドで定義されている比較処理にしたがってソートを行います。 上記の例ではキーを比較したため、Dictionaryはキーを基準にソートされました。 比較方法の定義を変えればソートの順序を変更することもできます。 例えば、CompareKeyValuePairを次のように変更することにより、Dictionaryを値でソートできるようになります。

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;
}
実行結果
Dave 1
Alice 2
Bob 3
Eve 4
Charlie 5

List.Sortメソッドと比較方法の定義(Comparison<T>デリゲート)については、複合型のソート・複数キーでのソートで詳しく解説します。

§1.5.2 キーと値の配列に変換してソートする

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を使ってDictionaryをソートする (キーと値の配列に変換してソートする)
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    // ソート対象のDictionary<string, int>
    Dictionary<string, int> 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の内容をコピー
    string[] sortedKeys = new string[dict.Count];
    int[] sortedValues = new int[dict.Count];

    dict.Keys.CopyTo(sortedKeys, 0);
    dict.Values.CopyTo(sortedValues, 0);

    // Array.Sort(Array, Array)メソッドを使ってソート
    Array.Sort(sortedKeys, sortedValues);

    for (int index = 0; index < sortedKeys.Length; index++) {
      Console.WriteLine("{0} {1}", sortedKeys[index], sortedValues[index]);
    }
  }
}
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

なお、Array.Sortに渡す配列はキーの配列・値の配列の順となっています。 この順序を逆に指定すれば、値でソートできるようになります。

Dictionaryを値でソートする場合のArray.Sortへの配列の指定順序
    :
    :
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

§1.5.3 OrderByを使ってソートする

拡張メソッドであるOrderByメソッドを使うことでもDictionaryをソートできます。 OrderByメソッドを使ったDictionaryのソートについては後述します。

§1.6 Enumerable.OrderBy

IEnumerable<T>インターフェイスを実装しているコレクションの場合、拡張メソッドであるOrderByを使うことによってソートする事ができます。

配列や、ListやDictionaryを含むジェネリックコレクションクラスはいずれもIEnumerable<T>を実装しているため、OrderByメソッドでソートする事ができます。

§1.6.1 OrderByメソッドの使い方と動作

OrderByメソッドを使って配列・Listをソートする例について見ていきます。

OrderByメソッドを使って配列をソートする
using System;
using System.Linq;

class Sample {
  static void Main()
  {
    // ソート対象の配列
    int[] arr = new int[] {5, 2, 3, 1, 4};

    // ソート
    IOrderedEnumerable<int> sorted = arr.OrderBy(val => val);

    // ソート後の結果を列挙して表示
    foreach (int val in sorted) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
OrderByメソッドを使ってListをソートする
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();
  }
}
実行結果
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メソッドの結果への影響で解説するように扱い方によっては意図に反する動作となる場合もあるので、遅延実行となることとその動作については把握しておく必要があります。

§1.6.2 OrderByメソッドとキーの選択

OrderByメソッドの引数keySelectorには、ソートの際に使用するキーを選択するメソッドへのデリゲート(またはラムダ式)を指定します。 先の例ではラムダ式を用いていましたが、これをメソッドとして展開すると次のようになります。

OrderByでのソートに使用されるキー選択のメソッドを指定する
using System;
using System.Linq;

class Sample {
  // ソートの際に使用するキーを選択するメソッド
  static int KeySelector(int val)
  {
    // 要素の値そのものをソートの際のキーとする
    return val;
  }

  static void Main()
  {
    // ソート対象の配列
    int[] arr = new int[] {5, 2, 3, 1, 4};

    // ソート
    IOrderedEnumerable<int> sorted = arr.OrderBy(KeySelector);

    foreach (int val in sorted) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}

OrderByメソッドの引数keySelectorとキー選択のメソッドについて詳しく見ていきます。

OrderByメソッドでは、ソートの際に何をキーとしてソートするかを引数keySelectorとして指定する必要があります。 これは、単純型でも複合型でもソートできるようにするために必要となるものです。 数値や文字列など単純型の配列・コレクションの場合は、単に要素そのもの(つまり数値の値や文字列自体)をキーとすればよいため、上記の例のように一見するとあまり意味のない記述となります。 しかし、Dictionaryや複合型の配列・コレクションの場合は、何を基準にソートするかによってキーを定める必要があるため、この引数が意味を持つようになります。

例として、文字列型のNameというプロパティを持つAccountクラスをソートしたい場合は、次のようにキー選択のメソッドを定義する必要があります。 この例を見れば、keySelectorの持つ意味が理解しやすくなると思います。

クラスのプロパティをソートのキーとするキー選択メソッド
// Accountクラスのソートの際に使用するキーを選択するメソッド
static string KeySelector(Account val)
{
  // Account.Nameプロパティの値をソートの際のキーとする
  return val.Name;
}

比較のために、先の例におけるキー選択のメソッドを抜粋します。 このメソッドでは、int/Integer型のソートをするために、そのキーとしてint/Integerの持つ値を選択しています。

intの値をソートのキーとするキー選択メソッド
static int KeySelector(int val)
{
  return val;
}

このように、keySelectorには引数にソート対象をとり、戻り値としてソート対象のキーを返すメソッド(またラムダ式)を指定します。

§1.6.3 OrderByメソッドを使ったDictionaryのソート

OrderByメソッドを使った具体的な例として、Dictionaryのソートを行う例について見てみます。

次の例のメソッドKeySelectorはキーの選択を行うメソッドです。 Dictionaryの場合は個々の要素がKeyValuePairとして格納されているため、KeyValuePairの何をキーとするかを定める必要があります。 Dictionaryをキーでソートするためには、KeyValuePair.Keyプロパティを並べ替えの際のキーとするようにします。 KeySelectorメソッドでは、このようなキー選択の動作を定義しています。 OrderByメソッドの引数にKeySelectorメソッドを渡すことにより、その定義にしたがってソートが行われます。

OrderByメソッドを使ってDictionaryをソートする
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>
    Dictionary<string, int> 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 (KeyValuePair<string, int> pair in sorted) {
      Console.WriteLine("{0} {1}", pair.Key, pair.Value);
    }
  }
}
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

上記の例ではDictionaryをキーにしたがってソートするためにKeyValuePair.Keyをキーとしていました。 一方、Dictionaryを値にしたがってソートしたい場合は、次のようにKeyValuePair.ValueをキーとするようにKeySelectorを変えるだけで出来ます(キーの型に合わせてメソッドの戻り値を変えている点に注意してください)。

OrderByメソッドを使って値の順にDictionaryをソートする場合のキー選択メソッド
static int KeySelector(KeyValuePair<string, int> pair)
{
  // 並べ替えの際のキーにValueの値を使用する
  return pair.Value;
}

比較のために、先の例をラムダ式を使ったものに書き換えると次のようになります。 OrderByメソッドで指定しているラムダ式は、上記の例におけるKeySelectorメソッドと同じ動作をします。 ラムダ式を使用すると、キーを選択するコードを個別のメソッドとして記述する必要がなくなるため、よりシンプルに記述できます。

OrderByメソッドを使ってDictionaryをソートする(ラムダ式版)
using System;
using System.Collections.Generic;
using System.Linq;

class Sample {
  static void Main()
  {
    // ソート対象のDictionary<string, int>
    Dictionary<string, int> 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 (KeyValuePair<string, int> pair in sorted) {
      Console.WriteLine("{0} {1}", pair.Key, pair.Value);
    }
  }
}

Dictionaryを値にしたがってソートしたい場合は、キー選択のラムダ式を次のように変更します。

OrderByメソッドを使って値の順にDictionaryをソートする場合のキー選択ラムダ式
dict.OrderBy(pair => pair.Value);

OrderByメソッドの代わりにOrderByDescendingメソッドを使うと、昇順ではなく降順でソートすることができます。

§1.6.4 元のコレクションに対する変更とOrderByメソッドの結果への影響

OrderByメソッドは遅延実行されるため、メソッドを呼び出した時点では結果は確定していません。 OrderByメソッドの戻り値を列挙する(もしくは配列・リストに変換する)時点ではじめて結果が確定します。

そのため、次の例のように、OrderByメソッドを呼び出してその結果が確定する前に元のコレクションに変更を加えると、その変更はソート後の結果にも影響するという点に注意が必要です。

ソート元のコレクションに対する変更とOrderByメソッドの結果への影響
using System;
using System.Collections.Generic;
using System.Linq;

class Sample {
  static void Main()
  {
    List<int> list = new List<int>(new int[] {
      3, 1, 2,
    });

    // ソート(この時点では結果が確定していない点に注意)
    IOrderedEnumerable<int> sorted = list.OrderBy(val => val);

    // 元になったリストに変更を加える
    list.Add(5);
    list.Add(4);

    // 列挙して結果を表示
    foreach (int val in sorted) {
      Console.Write("{0} ", val);
    }
    Console.WriteLine();
  }
}
実行結果
1 2 3 4 5 

上記のように、列挙する時点でソートが行われるため、OrderByを呼び出した後に追加した要素もソートされた上で列挙されます。

§2 降順でのソート

ここでは降順(大きい順)でのソートについて、いくつかの方法を見ていきます。

§2.1 Sort + Reverse

1つ目は、Sortメソッドで昇順にソートしてから、Reverseメソッドで逆順(つまり降順)にするものです。 配列・ArrayList・List<T>にはそれぞれArray.Reverse, ArrayList.Reverse, List.Reverseの各メソッドが用意されていて、これを使うことで要素を逆順に並び替える事が出来ます。

SortメソッドとReverseメソッドを使って配列を降順にソートする
using System;

class Sample {
  static void Main()
  {
    // ソート対象の配列
    int[] arr = new int[] {5, 2, 3, 1, 4};

    // ソート
    Array.Sort(arr);

    // リバース
    Array.Reverse(arr);

    foreach (int val in arr) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
SortメソッドとReverseメソッドを使ってListを降順にソートする
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();
  }
}
実行結果
5, 4, 3, 2, 1, 

Reverseメソッドそのものは単に要素を逆順に並び替えるだけなので、Reverseメソッドだけを呼び出しても降順には並び替えられません。 必ずSortメソッドで昇順にソートしてから呼び出す必要があります。

Reverseメソッドは、Array.SortList.Sortメソッドと同様、元になった配列・コレクション自体の内容を逆順にします(破壊的変更)。 非破壊的な方法で降順にソートしたい(元の配列・コレクションは維持したままにしたい)場合は、OrderByDescendingメソッドを使用することができます。

§2.2 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>デリゲートを使ってListを降順にソートする
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>
    List<int> list = new List<int>(new int[] {5, 2, 3, 1, 4});

    // ソート
    list.Sort(CompareDescending);

    foreach (int val in list) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果
5, 4, 3, 2, 1, 

SortメソッドとComparison<T>デリゲートについては、複合型のソート・複数キーでのソートでも改めて解説します。

Sortメソッドと型ごとのデフォルトのソート順については基本型とデフォルトのソート順で解説しています。

§2.3 OrderByDescending

3つ目は、拡張メソッドであるOrderByDescendingメソッドを使う方法です。 既に解説したOrderByメソッドは配列・コレクションを昇順にソートするものでしたが、OrderByDescendingメソッドは降順にソートするものです。

OrderByDescendingメソッドを使って配列を降順にソートする
using System;
using System.Linq;

class Sample {
  static void Main()
  {
    // ソート対象の配列
    int[] arr = new int[] {5, 2, 3, 1, 4};

    // 降順にソートして表示
    foreach (int val in arr.OrderByDescending(val => val)) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
OrderByDescendingメソッドを使ってListを降順にソートする
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();
  }
}
実行結果
5, 4, 3, 2, 1, 

降順にソートされる点を除けばOrderByDescendingメソッドはOrderByメソッドと同じなので、引数や動作について詳しくはOrderByメソッドについての解説を参照してください。

§3 シャッフル

ここまでは規則性のある順序でのソートを行ってきましたが、この順序をランダムにすることで配列やListをシャッフルすることが出来ます。 OrderByメソッドの場合、与えられたキーに基づいて並べ替えが行われますが、このキーにランダムな値を与えることでコレクションをシャッフルすることが出来ます。 次の例ではOrderByメソッドを使ってListをシャッフルしています。

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()
  {
    List<int> list = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9});

    foreach (int val in list.OrderBy(RandomKeySelector)) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果の例
9, 0, 6, 3, 4, 5, 8, 1, 7, 2, 

一方、Array.Sortメソッドではこのような方法は使えません。 次の例では、Array.Sortメソッドに毎回異なる結果を返すIComparer<T>を指定することで配列をシャッフルしようとしています。 IComparer<T>は、Comparison<T>デリゲートと同様の大小関係を定義するメソッドをクラスに実装するためのインターフェイスです。 大小関係をランダムにすることで一見シャッフル出来るように思えますが、実際にArray.Sortメソッドを呼び出すと、場合によっては大小関係に矛盾が生じて例外がスローされるため、期待通りには動作しません。

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()
  {
    int[] arr = new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    // シャッフル
    Array.Sort(arr, new RandomComparer());

    foreach (int val in arr) {
      Console.Write("{0}, ", val);
    }
    Console.WriteLine();
  }
}
実行結果の例 (大小関係に矛盾が生じなかった場合)
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>については大小関係の定義と比較を参照してください。

§4 パフォーマンスの比較

ここではソートを行ういくつかのケースについてパフォーマンスの比較を行った結果を紹介します。 比較メソッドの定義方法やソートするデータの種類等によっては結果が変わるので、ここで紹介している結果はあくまで参考程度のものです。

§4.1 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);
  }
}
実行結果 (Windows 7 + .NET Framework 4)
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
実行結果 (Ubuntu 11.10 + Mono 2.10.6)
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

複数のキーでソートした場合の結果については、複合型のソート・複数キーでのソート §.パフォーマンスの比較を参照してください。

§4.2 Sort+Reverse vs Sort(Comparison<T>) vs OrderByDescending

降順でソートするために、次の三つの方法をとり、それぞれの速度を比較してみます。

  1. SortメソッドとReverseメソッドを組み合わせる場合
  2. 降順にソートするComparison<T>を指定してSortメソッドを呼び出す場合
  3. 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);
  }
}
実行結果 (Windows 7 + .NET Framework 4)
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
実行結果 (Ubuntu 11.10 + Mono 2.10.6)
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