Home > Articles > Programming > C#

.NET Reference Guide

Hosted by

Toggle Open Guide Table of ContentsGuide Contents

Close Table of ContentsGuide Contents

Close Table of Contents

Sorting a Multi-Dimensional Array

Last updated Mar 14, 2003.

If you’re looking for more up-to-date information on this topic, please visit our .NET and Windows Programming article, podcast, and store pages.

Although the .NET Array class defines a Sort method, that method only sorts one-dimensional arrays. That's fine for most cases since the use of multi-dimensional arrays is relatively rare. In many .NET programs, tasks that traditionally have required multi-dimensional arrays are implemented using Table objects, and it's quite easy to create a sorted view of a table. But Table carries a lot of overhead, and it's not right for all situations. Sometimes you really do need to sort a two-dimensional (or N-dimensional) array.

Two types of multi-dimensional arrays

Multi-dimensional arrays come in two flavors: jagged arrays like those found in C and C++, and rectangular arrays as in Pascal and Visual Basic. Although only rectangular arrays are CLR compliant, both types are used in .NET programs. Read the linked topic for more details about the two types of arrays.

The two different array types make for two different ways to sort multi-dimensional arrays. In particular, it's possible to sort a jagged array (an array of arrays) using the standard Array.Sort method. To sort a rectangular array, you need to initialize a tag array, and then use that to sort the data array indirectly. You can also use the tag array technique to sort a jagged array.

Sorting a jagged array

A jagged array is, in effect, an array of arrays. It is defined and referenced like this:

[C#]

// declare and initialize a jagged array
int[][] a = new int[][] {
  new int[]{33, 12},
  new int[]{12, 10},
  new int[]{13,5},
  new int[]{27, 19}
};

// get the 2nd item in the 3rd row
Console.WriteLine(a[2][1]);

[Visual Basic]

' declare and initialize a jagged array
Dim a1() As Integer = {33, 12}
Dim a2() As Integer = {12, 10}
Dim a3() As Integer = {13, 5}
Dim a4() As Integer = {27, 19}
Dim a()() As Integer = {a1, a2, a3, a4}

' get the 2nd item in the 3rd row
Console.WriteLine(a(2)(1))

The default Sort method relies on the IComparable interface implemented by each element of the Array being sorted. That is, Sort calls the IComparable.CompareTo method of an element to compare it against another element in an array. In the case of a jagged array, the array elements are themselves arrays, and it doesn't make sense to compare two arrays directly. Attempting to do so will throw an exception. Therefore, it's impossible to sort the jagged array with a simple call to Array.Sort.

The IComparer Interface

Overloaded versions of Array.Sort allow you to pass as a parameter an object that implements the IComparer interface. This interface defines a single method, Compare (in the System.Collections namespace), which implementing classes define to compare two objects. It sounds kind of complicated, but it's actually quite simple if you take it in steps.

We have a multi-dimensional array of integers. In the case of a jagged array, the items in the first dimension are arrays of integers, so what we really have is an array of arrays of integers. What we need to do is implement an IComparer.Compare method that will compare two elements (integers) in the second dimension. So, for example, if we want to sort by the second column of numbers (12, 10, 5, 19), then our IComparer implementation would look like this:

[C#]

class JaggedComparer: IComparer
{
  public int Compare(object x, object y)
  {
	// x and y are arrays of integers
	// sort on the 2nd item in each array
	int[] a1 = (int[])x;
	int[] a2 = (int[])y;
	return (a1[1].CompareTo(a2[1]));
  }
}

[Visual Basic]

Class JaggedComparer
  Implements IComparer
    Public Function Compare(ByVal x As Object, ByVal y As Object) As Integer Implements IComparer.Compare
    ' x and y are arrays of integers
    ' sort on the 2nd item in each array
    Dim a1() As Integer = DirectCast(x, Integer())
    Dim a2() As Integer = DirectCast(y, Integer())
    Return a1(1).CompareTo(a2(1))
  End Function
End Class

This Compare method simply casts the passed Object references back to Array, and compares the second item by calling the item's CompareTo method. We know that the items in the array are integers, so it's safe to call the comparison method.

Using the IComparer is quite simple:

[C#]

// create the comparer and sort the array
JaggedComparer myComparer = new JaggedComparer();
Array.Sort(a, myComparer);

[Visual Basic]

' create the comparer and sort the array
Dim myComparer As New JaggedComparer
Array.Sort(a, myComparer)

Sorting a rectangular array

With a jagged array, it's possible to reference the first dimension as an array by itself. That is, you can assign to it. For example, this C# code is legal:

int[] testo = a[0];
a[1] = testo;

As a result, Array.Sort can swap array references as required in response to the values returned by the IComparer.Compare method.

You can't do that with a rectangular array. There's no way to "swap rows" in a rectangular array because the entire array is a single object rather than an array of one-dimensional arrays.

It's still possible to sort a rectangular array, but you have to do it indirectly. You have to create a second, one-dimensional array that contains the row numbers of the rectangular array. The IComparer.Compare method uses the passed row numbers to index into the rectangular array and sort the items.

Here's the code that creates the rectangular array and the tag array:

[C#]

int[,] a = new int[,] {{33, 12}, {12, 10}, {13, 5}, {27, 19}};
int[] tagArray = new int[] {0, 1, 2, 3};

[Visual Basic]

Dim a(,) As Integer = {{33, 12}, {12, 10}, {13, 5}, {27, 19}}
Dim tagArray() As Integer = {0, 1, 2, 3}

We can access the items in the multi-dimensional array indirectly through the tag array. For example, before sorting, the following two expressions access the same item:

a[0,1]
a[tagArray[0],1]

What we want to do is sort the tag array so that accessing a[tagArray[0],1] will give us the lowest item in the second column of the rectangular array. That is, a[2,1]. That's done by the IComparer implementation shown here:

[C#]

class RectangularComparer: IComparer
{
  // maintain a reference to the 2-dimensional array being sorted
  private int[,] sortArray;

  // constructor initializes the sortArray reference
  public RectangularComparer(int[,] theArray)
  {
    sortArray = theArray;
  }

  public int Compare(object x, object y)
  {
    // x and y are integer row numbers into the sortArray
    int i1 = (int)x;
    int i2 = (int)y;

    // compare the items in the sortArray
    return sortArray[i1,1].CompareTo(sortArray[i2,1]);
  }
}

[Visual Basic]

Class RectangularComparer
  Implements IComparer
  ' maintain a reference to the 2-dimensional array being sorted

  Private sortArray(,) As Integer

  ' constructor initializes the sortArray reference
  Public Sub New(ByVal theArray(,) As Integer)
    sortArray = theArray
  End Sub

  Public Function Compare(ByVal x As Object, ByVal y As Object) As Integer Implements IComparer.Compare
    ' x and y are integer row numbers into the sortArray
    Dim i1 As Integer = DirectCast(x, Integer)
    Dim i2 As Integer = DirectCast(y, Integer)

    ' compare the items in the sortArray
    Return sortArray(i1, 1).CompareTo(sortArray(i2, 1))
  End Function
End Class

The key concept here is that the IComparer implementation maintains a reference to the two dimensional array that contains the items to be sorted. However, the items in that array are never changed or swapped. Instead, the tag array is being sorted:

[C#]

int[,] a = new int[,] {{33, 12}, {12, 10}, {13, 5}, {27, 19}};
int[] tagArray = new int[] {0, 1, 2, 3};

// Initialize the comparer and sort
RectangularComparer myComparer = new RectangularComparer(a);
Array.Sort(tagArray, myComparer);

for (int i = 0; i < tagArray.Length; i++)
{
  Console.WriteLine(a[tagArray[i],1]);
}

[Visual Basic]

Dim a(,) As Integer = {{33, 12}, {12, 10}, {13, 5}, {27, 19}}
Dim tagArray() As Integer = {0, 1, 2, 3}
' Initialize the comparer and sort
Dim myComparer As New RectangularComparer(a)
Array.Sort(tagArray, myComparer)

Dim i As Integer
For i = 0 To tagArray.Length - 1
  Console.WriteLine(a(tagArray(i), 1))
Next

The only drawback to this technique is that you have to access the two-dimensional array indirectly, through the tag array. The only way to remove that restriction is to create a new two-dimensional array and copy the items from the old array to it, in order.

The benefit of the tag array approach is that it allows you to create multiple concurrent views, each sorted differently, into the same data. For example, you might want one tag array that orders the items by the first column, and another that orders them in reverse by the second column. That's not possible if you sort the array directly, but it is possible using the tag array method, and it will work for both jagged and rectangular arrays.