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:
v.OrderBy(x => x).ToArray().Show("ovi", "\r\nSorted by integer value");
v.OrderBy(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 string
s, 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.
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:
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 };
int[] v = ja[0];
v.Show("v", "\r\nInitial vector");
#region Initial vector output
#endregion
v.OrderBy(x => x).ToArray().Show("ovi", "\r\nSorted by integer value");
#region Sorted by integer value output
#endregion
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
#endregion
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
#endregion
ja.Show("ja", -999, "\r\n\r\nInitial jagged array");
#region Initial jagged array output
#endregion
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
#endregion
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
#endregion
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
#endregion
int[,] sortedByFirstElement = array.OrderBy(x => x[0]);
sortedByFirstElement.Show("array", "\r\nArray sorted by first element");
#region Array sorted by first element output
#endregion
int[,] sortedBySecondElement = array.OrderBy(x => x[1]);
sortedBySecondElement.Show("array", "\r\nArray sorted by second element");
#region Array sorted by second element output
#endregion
int[,] sortedByThirdElement = array.OrderBy(x => x[2]);
sortedByThirdElement.Show("array", "\r\nArray sorted by third element");
#region Array sorted by third element output
#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
- 19th March, 2011: Initial version
I have been doing database related programming in the financial services industry for over 20 years on various platforms. I used to be a UNIX Sybase DBA but now prefer programming in the .NET environment using C# and SQL Server.