ここでは、Array.Sortメソッドでジャグ配列(多段配列・配列の配列)および多次元配列をソートする方法について解説します。

Array.Sortメソッドではジャグ配列全体をそのままソートすることはできず、ソート順序の定義を行う必要があります。 ジャグ配列が矩形(ジャグ配列内の全ての配列の長さが同じ)の場合はStructuralComparisons.StructuralComparerを指定することでソートすることができます。

また、Array.Sortメソッドは多次元配列のソートをサポートしていないため、多次元配列をジャグ配列に変換してからソートするなどの方法をとる必要があります。

§1 ジャグ配列のソート

Array.Sortメソッドは任意の配列(Arrayクラス)を引数に取るため、ジャグ配列を指定することもできます。 しかし、単にジャグ配列を指定するだけではジャグ配列をソートすることは出来ません。 ジャグ配列をソートしようとすると、例外InvalidOperationExceptionがスローされます。

これは、ソートの際にジャグ配列内の個々の要素(つまりジャグ配列内の配列同士)を比較しようとするものの、配列同士をそのまま比較することができないことにより例外がスローされるためです。 そこで、複合型のソート・複数キーでのソートでも解説しているように、配列同士の比較を行うメソッドを用意し、それをArray.Sortメソッドに指定することでジャグ配列のソートが出来るようになります。

早速、次のような2段のジャグ配列(配列の配列)をソートする場合について見ていきます。

以下のジャグ配列をソートしたい
int[][] arr = new int[][] {
  new int[] {1, 2},
  new int[] {2, 1},
  new int[] {2, 1, 1},
  new int[] {1, 2, 2, 2},
  new int[] {1, 1},
  new int[] {1, 3},
  new int[] {1, 2, 3},
  new int[] {1, 2, 2},
  new int[] {2, 2},
  new int[] {2, 1, 1},
};

以降、このジャグ配列をソートして次のように並べ替えることを考えます。

ソート後に得たい結果
1, 1, 
1, 2, 
1, 2, 2, 
1, 2, 2, 2, 
1, 2, 3, 
1, 3, 
2, 1, 
2, 1, 1, 
2, 1, 1, 
2, 2, 

まず、Array.Sortメソッドを使用して任意の型をソートする際、ソート対象に加えソート対象の要素同士の比較を行うメソッド(comparer)を指定する必要があります。 要素の比較を行うメソッドでは、引数として渡される二つの要素xyについて、その大小関係に従って次のような値を返すように実装する必要があります。

  • x > y ならば 正の数
  • x < y ならば 負の数
  • x = y ならば 0

ジャグ配列のソートの場合、ジャグ配列内の各配列を比較して並べ替えることになるため、要素xyはジャグ配列内の各配列となります。 また、ジャグ配列の場合はそれぞれ長さの異なる配列を含めることができるため、ここでは二つの配列の大小関係を次のように定めることにします。

  • 二つの配列x, yの長さのうち、小さい方の長さをminとする (min = Math.Min(x.Length, y.Length))
  • 二つの配列の要素を先頭からmin番目まで一つずつ比較し、n番目の要素について
    • x[n] > y[n] ならば x > y とする (正の数を返す)
    • x[n] < y[n] ならば x < y とする (負の数を返す)
  • min番目までの要素がすべて同じだった場合、配列x, yの長さについて
    • x.Length > y.Length ならば x > y とする (正の数を返す)
    • x.Length < y.Length ならば x < y とする (負の数を返す)
    • x.Length = y.Length ならば x = y とする (0を返す)

この大小関係に従ってジャグ配列をソートするコードを実装すると、次のようになります。

2段のジャグ配列をソートする
using System;

class Sample {
  // 長さが異なる二つの配列を比較するメソッド
  // (このメソッドでジャグ配列内の各配列同士を比較する際の動作を定義する)
  static int CompareArray(int[] x, int[] y)
  {
    int min = Math.Min(x.Length, y.Length);

    for (int n = 0; n < min; n++) {
      if (x[n] > y[n])
        return 1;
      else if (x[n] < y[n])
        return -1;
    }

    if (x.Length > y.Length)
      return 1;
    else if (x.Length < y.Length)
      return -1;
    else /* if (x.Length == y.Length) */
      return 0;
  }

  static void Main()
  {
    int[][] arr = new int[][] {
      new int[] {1, 2},
      new int[] {2, 1},
      new int[] {2, 1, 1},
      new int[] {1, 2, 2, 2},
      new int[] {1, 1},
      new int[] {1, 3},
      new int[] {1, 2, 3},
      new int[] {1, 2, 2},
      new int[] {2, 2},
      new int[] {2, 1, 1},
    };

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

    for (int y = 0; y < arr.Length; y++) {
      for (int x = 0; x < arr[y].Length; x++) {
        Console.Write("{0}, ", arr[y][x]);
      }
      Console.WriteLine();
    }
  }
}
実行結果
1, 1, 
1, 2, 
1, 2, 2, 
1, 2, 2, 2, 
1, 2, 3, 
1, 3, 
2, 1, 
2, 1, 1, 
2, 1, 1, 
2, 2, 

このように、2段のジャグ配列(配列の配列)をソートするには配列同士の大小関係を定義して比較する必要があります。 3段以上のジャグ配列の場合も同様で、例えば3段のジャグ配列(配列の配列の配列)なら2段のジャグ配列(配列の配列)同士の大小関係を定義する必要があります。

§1.1 StructuralComparisons.StructuralComparerを使った矩形ジャグ配列のソート

.NET Framework 4より導入されたStructuralComparisons.StructuralComparerを使うことでもジャグ配列をソートすることが出来ます。 ただし、ソート出来るのはジャグ配列内の各配列の長さが等しい場合(=矩形のジャグ配列)に限られます。

次の例は、StructuralComparisons.StructuralComparerを使って2段のジャグ配列をソートする例です。

StructuralComparisons.StructuralComparerを使って2段の矩形ジャグ配列をソートする
using System;
using System.Collections;

class Sample {
  static void Main()
  {
    int[][] arr = new int[][] {
      new int[] {1, 2, 1},
      new int[] {2, 1, 1},
      new int[] {2, 2, 1},
      new int[] {2, 1, 1},
      new int[] {2, 1, 2},
      new int[] {1, 2, 3},
      new int[] {1, 1, 1},
      new int[] {1, 2, 2},
    };

    // StructuralComparisons.StructuralComparerを指定してジャグ配列をソート
    Array.Sort(arr, StructuralComparisons.StructuralComparer);

    for (int y = 0; y < arr.Length; y++) {
      for (int x = 0; x < arr[y].Length; x++) {
        Console.Write("{0}, ", arr[y][x]);
      }
      Console.WriteLine();
    }
  }
}
実行結果
1, 1, 1, 
1, 2, 1, 
1, 2, 2, 
1, 2, 3, 
2, 1, 1, 
2, 1, 1, 
2, 1, 2, 
2, 2, 1, 

StructuralComparisonsについては構造の比較で詳しく解説しています。

§1.2 ジャグ配列内の各配列のソート

単にジャグ配列内の各配列をソートしたい(各配列の位置は変えない)のであれば、次の例のように個々の配列に対してSortメソッドを呼び出すだけで出来ます。

ジャグ配列内の各配列をソートする
using System;

class Sample {
  static void Main()
  {
    int[][] arr = new int[][] {
      new int[] {1, 2},
      new int[] {2, 1},
      new int[] {2, 1, 1},
      new int[] {1, 2, 2, 2},
      new int[] {1, 1},
      new int[] {1, 3},
      new int[] {1, 2, 3},
      new int[] {1, 2, 2},
      new int[] {2, 2},
      new int[] {2, 1, 1},
    };

    // ジャグ配列内の各配列をソート
    foreach (int[] subarr in arr) {
      Array.Sort(subarr);
    }

    for (int y = 0; y < arr.Length; y++) {
      for (int x = 0; x < arr[y].Length; x++) {
        Console.Write("{0}, ", arr[y][x]);
      }
      Console.WriteLine();
    }
  }
}
実行結果
1, 2, 
1, 2, 
1, 1, 2, 
1, 2, 2, 2, 
1, 1, 
1, 3, 
1, 2, 3, 
1, 2, 2, 
2, 2, 
1, 1, 2, 


§2 多次元配列のソート

ジャグ配列の場合と同様、多次元配列もArray.Sortメソッドではソートすることは出来ません。 そもそもArray.Sortメソッドは1次元配列のみのソートしかサポートしていないため、Comparison<T>を指定しても多次元配列ソートすることは出来ず、RankExceptionがスローされます。 そこで、多次元配列をソートするには、一旦すべての要素を1次元配列に展開してからソートするか、次元毎に展開してジャグ配列に変換してからソートするなどの方法をとる必要があります。

次の例では、2次元配列を2段のジャグ配列に変換してからソートを行っています。 ジャグ配列のソートについては§.ジャグ配列のソートで解説したとおりですが、多次元配列から作成したジャグ配列は各次元の配列の長さが同じとなるため、長さが異なる場合を考慮する必要がなくなります。

2段のジャグ配列に変換して2次元配列をソートする
using System;

class Sample {
  // 2次元配列を2段のジャグ配列に変換
  static int[][] ToJaggedArray(int[,] arr)
  {
    // 2段のジャグ配列を作成
    int[][] jagged = new int[arr.GetLength(0)][];

    for (int y = 0; y < arr.GetLength(0); y++) {
      // 配列を作成してジャグ配列内に格納
      jagged[y] = new int[arr.GetLength(1)];

      for (int x = 0; x < arr.GetLength(1); x++) {
        // 2次元配列の内容を作成したジャグ配列にコピー
        jagged[y][x] = arr[y, x];
      }
    }

    return jagged;
  }

  // 長さが同じ二つの配列を比較するメソッド
  static int CompareArray(int[] x, int[] y)
  {
    for (int n = 0; n < x.Length; n++) {
      if (x[n] > y[n])
        return 1;
      else if (x[n] < y[n])
        return -1;
    }

    return 0;
  }

  static void Main()
  {
    int[,] arr = new int[,] {
      {1, 2, 1},
      {2, 1, 1},
      {2, 2, 1},
      {2, 1, 1},
      {2, 1, 2},
      {1, 2, 3},
      {1, 1, 1},
      {1, 2, 2},
    };

    // ジャグ配列に変換
    int[][] jagged = ToJaggedArray(arr);

    // 変換したジャグ配列をソート
    Array.Sort(jagged, CompareArray);

    for (int y = 0; y < jagged.Length; y++) {
      for (int x = 0; x < jagged[y].Length; x++) {
        Console.Write("{0}, ", jagged[y][x]);
      }
      Console.WriteLine();
    }
  }
}
実行結果
1, 1, 1, 
1, 2, 1, 
1, 2, 2, 
1, 2, 3, 
2, 1, 1, 
2, 1, 1, 
2, 1, 2, 
2, 2, 1, 

§3 キー・値ペアの配列のソート

一つの二次元配列に入ったデータをソートするのではなく、二つの互いに関連するデータが格納された配列をソートするのであれば、Array.Sortメソッドを使うことが出来ます。 Array.Sortメソッドには配列を二つ引数にとるバージョンのオーバーロードが用意されていて、これを用いると一方の配列の値をキーとしてもう一方の配列をソートすることが出来ます。 これは基本型のソートと昇順・降順でのソート §.Dictionaryのソートでも解説しているもので、キーと値の関係にある二つの配列をソートするために使えます。

次の例では、このメソッドを使い、次の表のようにIDと名前からなるデータをそれぞれ個別の配列に格納し、IDの順に名前の配列をソートしています。

ID (int[]) Name (string[])
5 "Charlie"
3 "Bob"
2 "Alice"
4 "Eve"
1 "Dave"
キー・値ペアの配列をソートする
using System;

class Sample {
  static void Main()
  {
    int[] ids = new int[] {5, 3, 2, 4, 1};
    string[] names = new string[] {"Charlie", "Bob", "Alice", "Eve", "Dave"};

    // IDをキーとして名前の配列をソート
    Array.Sort(ids, names);

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