Sorting generic multi-dimensional array

[JC]

Hi all,

I have scoured the internet for articles on sorting multi-dimensional
arrays of generic types e.g. T[][] using the IComparer<T> interface
and have run into a real roadblack. There does not seem to be an easy
way to do this. I have found implementations that use the non-generic
IComparer interface but it seems to me to be more elegant to use
generics if possible.

Has anyone else had this problem and could they suggest or poin me
towards a possible solution?

Thanks in advance

 

[Marc Gravell]

First: T[][] isn't a multi-dimensional array; it is a jagged array.

How exactly do you want to sort the data? Do you have an example?
(perhaps just using integers for simplicity...)

You can use Array.Sort on a jagged array to sort individual inner
arrays, and (separately) to sort the outer array - but you can't use
it to sort the array as a rectangle. AFAIK, even with a rectangular
array you can't do that.

Perhaps if you provide a (simple) example it will become clearer what
you want?

For example, the following sorts within each row ordinally, and sorts
the rows by the item count:

int[][] data = new int[][] {
new int[] {3,4,1},
new int[] {1,5,6,2},
new int[] {0},
new int[] {1,4}
};
for (int i = 0; i < data.Length; i++)
{
Array.Sort(data);
}
Array.Sort(data, (x, y) => x.Length.CompareTo(y.Length));
for (int i = 0; i < data.Length; i++)
{
for (int j = 0; j < data.Length; j++)
{
Console.Write(data[j]);
Console.Write('\t');
}
Console.WriteLine();
}

Marc

 

[Marc Gravell]

BTW - if you need, you can get the ordinal comparer via
Comparer<T>.Default

Marc

 

[JC]

BTW - if you need, you can get the ordinal comparer via
Comparer<T>.Default

Marc

Thanks to both responses. I will try the default comparer as
suggested here. As for an example, basically the jagged arrays (picky
syntax boy! ) being generated hold permutations of objects, in my
case these are integers:

I want to ensure that these are sorted in lexicographic order so each
"row" as it were needs to be compared to each other "row".

So: I want:

|1|2|3|
|2|3|4|
|2|3|1|

to become

|1|2|3|
|2|3|1|
|2|3|4|

where the second and third rows get swapped. I have seen this
referred to as flat sorting of multidimensional (or jagged to be
specific) arrays.

Does that help for an example?

Thanks!

 

[Marc Gravell]

Does that help for an example?

Yes. And btw, the language matters here, because this wouldn't be
possible with a rectangular array:

using System;
using System.Collections;
using System.Collections.Generic;
static class Program {
static void Main() {
int[][] data = new int[][] {
new int[] {1,2,3},
new int[] {2,3,4},
new int[] {2,3,1}
};
Sort<int>(data);
foreach (int[] row in data)
{
foreach (int cell in row)
{
Console.Write(cell);
Console.Write('\t');
}
Console.WriteLine();
}
}
private static void Sort<T>(T[][] data)
{
Array.Sort<T[]>(data, CompareRows<T>);
}

private static int CompareRows<T>(T[] x, T[] y)
{
int len = x.Length > y.Length ? y.Length : x.Length; // max
length
IComparer<T> comparer = Comparer<T>.Default;
for (int i = 0; i < len; i++)
{
int delta = comparer.Compare(x, y);
if (delta != 0) return delta;
}
// if same in the overlapping portion, compare by size instead
return x.Length.CompareTo(y.Length);
}
}

 

[JC]

Thank you muchly!

I cracked it just before checking this by doing roughly the same thing
as you (except using an anonymous delegate). I like the IComparer
much more though so will adapt my solution. Thanks again!

Does that help for an example?

Yes. And btw, the language matters here, because this wouldn't be
possible with a rectangular array:

using System;
using System.Collections;
using System.Collections.Generic;
static class Program {
    static void Main() {
        int[][] data = new int[][] {
            new int[] {1,2,3},
            new int[] {2,3,4},
            new int[] {2,3,1}
        };
        Sort<int>(data);
        foreach (int[] row in data)
        {
            foreach (int cell in row)
            {
                Console.Write(cell);
                Console.Write('\t');
            }
            Console.WriteLine();
        }
    }
    private static void Sort<T>(T[][] data)
    {
        Array.Sort<T[]>(data, CompareRows<T>);
    }

    private static int CompareRows<T>(T[] x, T[] y)
    {
        int len = x.Length > y.Length ? y.Length : x.Length; //max
length
        IComparer<T> comparer = Comparer<T>.Default;
        for (int i = 0; i < len; i++)
        {
            int delta = comparer.Compare(x, y);
            if (delta != 0) return delta;
        }
        // if same in the overlapping portion, compare by size instead
        return x.Length.CompareTo(y.Length);
    }

}