• Download source - 3.81 KB

Background

I needed to sort a two-dimensional array for a project recently so I scoured the Net looking for a prebuilt routine to do so. I didn't find one, but I did find an algorithm published as a response to someone else's query. I created a plug and play sort routine using those ideas and published it as a CodeProject tip here.

I got a great response from Andrew Rissing who provided a solution, reproduced below, based on extension methods and LINQ, which was the catalyst for this article.

Extension Methods

In the spirit of this article, I have created some extension methods, all called Show, which are used to display the various arrays. Although making them extension methods was unnecessary, it does make for a nice "flow" of operations where the output of the previous method is the input to the subsequent one. So instead of writing Show(v.OrderBy()...), you write v.OrderBy()...Show(). Not a big deal for the Show method but using the built-in LINQ OrderBy and OrderByDescending extension methods gives us an easy way to order a vector (a one-dimensional array).

Sorting a vector may be a given but beyond that you are on your own. Andrew has provided the methods to sort a standard two-dimensional array and I have extrapolated that solution to provide an extension method for sorting a two-dimensional jagged array as well.

Sorting A Vector

Here are two examples of sorting a vector using the OrderBy extension method:

// To order a sequence by the values of the elements themselves, 
// specify the identity function (x => x)
v.OrderBy(x => x).ToArray().Show("ovi", "\r\nSorted by integer value");

// Use a function F(x) to convert the number argument x to a string based on its spelling
v.OrderBy<int>(x => F(x)).ToArray().Show("ovci", "\r\nCase insensitive 
	ordering of number's spelling");

Note that in the second example, I have provided my own function which converts a numeric value into a string. As such, I use the OrderBy<int, string> generic method indicating that the output will be an enumeration of strings, not integers. The first OrderBy defaults to v.OrderBy<int, int> because v is an integer vector. The OrderBy defines the sort, but it is not executed until the ToArray() method is called.

Sorting A Two-Dimensional Jagged Array

Sorting a jagged array is relatively easy and it provides an insight into Andrew's more complicated solution. The key to sorting a two-dimensional array is to enumerate each inner row of the array. For a jagged array, I provided this simple extension method to do just that:

private static IEnumerable<T[]> EnumerateInnerVectors<T>(this T[][] source)
{
    for (int i=0; i <= source.GetUpperBound(0); i++)
        yield return source[i];
}

The built-in OrderBy method works on an enumeration of the items to sort. For a vector that is simply the elements of the vector, so you use the Lambda expression 'x => x' to sort on the element itself. For a jagged array, the element to be sorted (enumerated) is a vector since a jagged array is simply a vector of vectors. Consequently, since we want the ordering of each of the vector "rows" of the array to be based on the value of a specific column, we must specify that column as the sort value in the Lambda expression. For example, 'x => x[1]' says to sort on the (0-order) second column value of each inner row (the second dimension of the jagged array) which is what we are returning in the above routine.

Sorting A Non-jagged Two-Dimensional Array

This is a bit more complicated since it requires the additional steps of converting the array to a jagged array first, sorting that, and then reconverting the jagged array to its original form. Andrew's OrderBy extension method is similar to the buit-in LINQ method. It first converts the source array to an enumeration of its inner row vectors, sets the ordering via the built-in OrderBy(keySelector) method, and then does the sort and conversion back to a normal array in ConvertToMultiDimensional.

Here are some of the more important extension methods that do the work. Check out the program source for all of the code.

////////////////////////////////////////////////////////////
// The following code was written by Andrew Rissing
// (http://www.codeproject.com/script/Membership/View.aspx?mid=1431085) //
/////////////////////////////////////////////////////////////////////////////

public static T[,] OrderBy<T>(this T[,] source, Func<T[], T> keySelector)
{
    return source.ConvertToSingleDimension().OrderBy(keySelector).
	ConvertToMultiDimensional();
}

public static T[,] OrderByDescending<T>(this T[,] source, Func<T[], T> keySelector)
{
    return source.ConvertToSingleDimension().OrderByDescending
    	(keySelector).ToArray().ConvertToMultiDimensional();
}

private static IEnumerable<T[]> ConvertToSingleDimension<T>(this T[,] source)
{
    T[] arRow;
    for (int row = 0; row < source.GetLength(0); ++row)
    {
         arRow = new T[source.GetLength(1)];
         for (int col = 0; col < source.GetLength(1); ++col)
         arRow[col] = source[row, col];
         yield return arRow;
    }
}

private static T[,] ConvertToMultiDimensional<T>(this IEnumerable<T[]> source)
{
    T[,] twoDimensional;
    T[][] arrayOfArray;
    int numberofColumns;
    arrayOfArray = source.ToArray();
    numberofColumns = (arrayOfArray.Length > 0) ? arrayOfArray[0].Length : 0;
    twoDimensional = new T[arrayOfArray.Length, numberofColumns];
    for (int row = 0; row < arrayOfArray.GetLength(0); ++row)
    for (int col = 0; col < numberofColumns; ++col)
    twoDimensional[row, col] = arrayOfArray[row][col];
    return twoDimensional;
}

And here are the examples with the output embedded so you can see the results:

// Create a jagged array
int[][] ja = new int[3][];
ja[0] = new int[] { 9, 7, 3, 8, 0, 6, 1, 2 };
ja[1] = new int[] { 8, 6, 4, 3 };
ja[2] = new int[] { 6, 9 };

// Create a vector
int[] v = ja[0];

v.Show("v", "\r\nInitial vector");
// To order a sequence by the values of the elements themselves,
// specify the identity function (x => x)
#region Initial vector output
// *****
// v[0] = 9,    v[1] = 7,    v[2] = 3,    v[3] = 8,
// v[4] = 0,    v[5] = 6,    v[6] = 1,    v[7] = 2,
// *****
#endregion
v.OrderBy(x => x).ToArray().Show("ovi", "\r\nSorted by integer value");
#region Sorted by integer value output
// *****
// ovi[0] = 0,    ovi[1] = 1,    ovi[2] = 2,    ovi[3] = 3,
// ovi[4] = 6,    ovi[5] = 7,    ovi[6] = 8,    ovi[7] = 9,
// *****
#endregion
// Use the function F(x) to convert the number argument x
// to a string based on its spelling
v.OrderBy<int, string>(x => F(x)).ToArray().Show
	("ovci", "\r\nCase insensitive ordering of number's spelling");
#region Case insensitive ordering of number`s spelling output 
// *****
// ovci[0] = 8,    ovci[1] = 9,    ovci[2] = 1,    ovci[3] = 7,
// ovci[4] = 6,    ovci[5] = 3,    ovci[6] = 2,    ovci[7] = 0,
// *****
#endregion
// Use the string version of the generic Comparer class
// to order the results in case sensitive order
v.OrderBy<int, string>(x => F(x), new Comparer<string>()).ToArray().Show
("ovcs", "\r\nCase sensitive ordering -- even numbers first");
#region Case sensitive ordering -- even numbers first output
// *****
// ovcs[0] = 8,    ovcs[1] = 6,    ovcs[2] = 2,    ovcs[3] = 0,
// ovcs[4] = 9,    ovcs[5] = 1,    ovcs[6] = 7,    ovcs[7] = 3,
// *****
#endregion

ja.Show("ja", -999, "\r\n\r\nInitial jagged array");
#region Initial jagged array output
// *****
// ja[0][0] = 9,    ja[0][1] = 7,    ja[0][2] = 3,    ja[0][3] = 8,
// ja[0][4] = 0,    ja[0][5] = 6,    ja[0][6] = 1,    ja[0][7] = 2,
// ja[1][0] = 8,    ja[1][1] = 6,    ja[1][2] = 4,    ja[1][3] = 3,
// ja[2][0] = 6,    ja[2][1] = 9,
// *****
#endregion
// EnumerateInnerVectors returns an enumeration of the vectors
// representing the "rows" of the jagged array
// Argument 1 specifies to pad each row to 8 elements with a
// value of -999 (representing a missing value)
// The lambda expression x => x[1] orders the enumerated
// vectors based on the second column value
int[][] oa = ja.EnumerateInnerVectors(8, -999).OrderByDescending
	(x => x[1]).ToArray();
oa.Show("oja1d", -999, "\r\nJagged array ordered in
	descending order on the second column");
#region Jagged array ordered in descending order
	on the second column output
// *****
// oja1d[0][0] = 6,    oja1d[0][1] = 9,    oja1d[0][2] = -,
// oja1d[0][3] = -,    oja1d[0][4] = -,    oja1d[0][5] = -,
// oja1d[0][6] = -,    oja1d[0][7] = -,
// oja1d[1][0] = 9,    oja1d[1][1] = 7,    oja1d[1][2] = 3,
// oja1d[1][3] = 8,    oja1d[1][4] = 0,    oja1d[1][5] = 6,
// oja1d[1][6] = 1,    oja1d[1][7] = 2,
// oja1d[2][0] = 8,    oja1d[2][1] = 6,    oja1d[2][2] = 4,
// oja1d[2][3] = 3,    oja1d[2][4] = -,    oja1d[2][5] = -,
// oja1d[2][6] = -,    oja1d[2][7] = -,
// *****
#endregion

// Order the rows based on the value of the fifth column of each vector
ja.EnumerateInnerVectors(5, -999).OrderBy(x => x[4]).ToArray()
.Show("oj4a", -999, "\r\nJagged array ordered in ascending order on the fifth column");
#region Jagged array ordered in ascending order on the fifth column output
// *****
// oj4a[0][0] = 8,    oj4a[0][1] = 6,    oj4a[0][2] = 4,
// oj4a[0][3] = 3,    oj4a[0][4] = -,
// oj4a[1][0] = 6,    oj4a[1][1] = 9,    oj4a[1][2] = -,
// oj4a[1][3] = -,    oj4a[1][4] = -,
// oj4a[2][0] = 9,    oj4a[2][1] = 7,    oj4a[2][2] = 3,
// oj4a[2][3] = 8,    oj4a[2][4] = 0,    oj4a[2][5] = 6,
// oj4a[2][6] = 1,    oj4a[2][7] = 2,
// *****
#endregion

// Sorting a two-dimensional array
int[,] array = new int[3, 3] { { 9, 1, 4 }, { 4, 5, 1 }, { 7, 3, 8 } };
array.Show("array", "\r\nInitial 2 dimensional array");
#region Initial 2 dimensional array output
// *****
// array[0][0] = 9,    array[0][1] = 1,    array[0][2] = 4,
// array[1][0] = 4,    array[1][1] = 5,    array[1][2] = 1,
// array[2][0] = 7,    array[2][1] = 3,    array[2][2] = 8,
// *****
#endregion

int[,] sortedByFirstElement = array.OrderBy(x => x[0]);
sortedByFirstElement.Show("array", "\r\nArray sorted by first element");
#region Array sorted by first element output
// *****
// array[0][0] = 4,    array[0][1] = 5,    array[0][2] = 1,
// array[1][0] = 7,    array[1][1] = 3,    array[1][2] = 8,
// array[2][0] = 9,    array[2][1] = 1,    array[2][2] = 4,
// *****
#endregion
int[,] sortedBySecondElement = array.OrderBy(x => x[1]);
sortedBySecondElement.Show("array", "\r\nArray sorted by second element");
#region Array sorted by second element output
// *****
// array[0][0] = 9,    array[0][1] = 1,    array[0][2] = 4,
// array[1][0] = 7,    array[1][1] = 3,    array[1][2] = 8,
// array[2][0] = 4,    array[2][1] = 5,    array[2][2] = 1,
// *****
#endregion
int[,] sortedByThirdElement = array.OrderBy(x => x[2]);
sortedByThirdElement.Show("array", "\r\nArray sorted by third element");
#region Array sorted by third element output
// *****
// array[0][0] = 4,    array[0][1] = 5,    array[0][2] = 1,
// array[1][0] = 9,    array[1][1] = 1,    array[1][2] = 4,
// array[2][0] = 7,    array[2][1] = 3,    array[2][2] = 8,
// *****
#endregion

Although all of the important stuff is contained here, you can download the attached program to see all of the code and play with it. As a (former) non-LINQ user, Andrew's code piqued my curiosity and I hope it has interested you as well, particularly if you are not currently writing LINQ code.

History

• 19^th March, 2011: Initial version