Click here to Skip to main content
Click here to Skip to main content

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

, 30 Mar 2011
Rate this:
Please Sign up or sign in to vote.
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

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

Comments and Discussions

 
GeneralMy vote of 5 Pinmemberthepbac30-Mar-11 16:22 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140821.2 | Last Updated 30 Mar 2011
Article Copyright 2011 by Tony Zackin
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid