11,712,454 members (72,463 online)

# Using LINQ and Extension Methods in C# to Sort Vectors and Two-Dimensional Arrays

, 30 Mar 2011 CPOL 17.5K 192 16
 Rate this:
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 `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.

```////////////////////////////////////////////////////////////
// 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

## Share

 Software Developer (Senior) Takamomto, LLC United States
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.

## You may also be interested in...

 First Prev Next
 My vote of 5 thepbac30-Mar-11 16:22 thepbac 30-Mar-11 16:22
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Sep-15 9:23 Refresh 1