Using LINQ and Extension Methods in C# to Sort Vectors and Two-Dimensional Arrays
4.71/5 (6 votes)
This article explains and shows examples of using LINQ and extension methods for array sorting
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(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
- 19th March, 2011: Initial version