Efficiently sort the following?

arnold_w

I am working with C# and I have a tab control with several tab pages (tab pages T0, T1, T2, etc). On each tab page there are group boxes ("etched borders"), each with a heading (heading H0, H1, H2, etc). In each group box there are labels (L0, L1, L2, etc). The tab controls, headings, and labels are specified randomly in a table: T0 H0 L2 T1 H2 L1 T0 H1 L4 T0 H0 L0 T2 H4 L2 T2 H3 L6 I need to sort these like this: T0 H0 L2 T0 H0 L0 T0 H1 L4 T1 H2 L1 T2 H4 L2 T2 H3 L6 Does anybody know what algorithm I should a look into?

Lost User

What is the rule according which they have been ordered?

arnold_w

The first row in the table dictates what label should be in the first group box in the first tab page. Then, all other labels that belong in same the tab page and group box are added in the order they appear in the original table. When no more labels belong to the first group box in the first tab page, then second group box in the first tab page are added in the order they appear in the original table. Then the third group box is processed, then the fourth, etc until there are no more group boxes in the first tab. Then same algorithm applies same way to the second tab page, then the third tab page, then the fourth, etc.

Lost User

That looks to be just a simple sort using the T field as the first key, and the H field as the second. Er, except the last two entries.

Richard Deeming

I'm not sure it's particularly efficient, but using LINQ, you can at least get the right answer. :)

struct Record
{
public int T { get; set; }
public int H { get; set; }
public int L { get; set; }
}

Record[] UnsortedRecords =
{
new Record { T = 0, H = 0, L = 2 },
new Record { T = 1, H = 2, L = 1 },
new Record { T = 0, H = 1, L = 4 },
new Record { T = 0, H = 0, L = 0 },
new Record { T = 2, H = 4, L = 2 },
new Record { T = 2, H = 3, L = 6 },
};

public static IEnumerable<Record> SortRecords(IEnumerable<Record> source)
{
return source
.GroupBy(r => r.T, (key, items) => items
.GroupBy(r => r.H)
.SelectMany(g => g)
)
.SelectMany(g => g);
}

IEnumerable<Record> SortedRecords = SortRecords(UnsortedRecords);

/*
Sorted records:

T0 H0 L2
T0 H0 L0
T0 H1 L4
T1 H2 L1
T2 H4 L2
T2 H3 L6
*/

NB: The documentation for GroupBy states that the order of the input sequence is preserved by both the returned groups, and the items within each group:

Enumerable.GroupBy[^]:

The IGrouping<TKey,TElement> objects are yielded in an order based on the order of the elements in source that produced the first key of each IGrouping<TKey,TElement>. Elements in a grouping are yielded in the order they appear in source.

You might be tempted to use a composite key in the grouping, to reduce the nesting. But that won't work - T0H1 and T1H2 will be returned in the wrong order:

source.GroupBy(r => new { r.T, r.H }).SelectMany(g => g);

/*
Result:

T0 H0 L2
T0 H0 L0
T1 H2 L1
T0 H1 L4
T2 H4 L2
T2 H3 L6
*/

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

arnold_w

This seems to be exactly what I need. Does anybody know how I can implement this in Visual Studio 2005? Or, does anybody know how I can convert my traditional ArrayList into an IEnumerable? The contents of my ArrayList are objects of a class containing about 20 different variables (out of which 3 are strings representing tab page, group box, and label).

Richard Deeming

You can use LINQBridge[^] to bring the LINQ methods into C# 2.0, although the syntax is nowhere near as clean:

public static IEnumerable<Record> SortRecords(IEnumerable<Record> source)
{
IEnumerable<IEnumerable<Record>> groupT = Enumerable.GroupBy(source,
delegate(Record r) { return r.T; },
delegate(int key, IEnumerable<Record> items)
{
IEnumerable<IGrouping<int, Record>> groupH = Enumerable.GroupBy(items, delegate(Record r) { return r.H; });
return Enumerable.SelectMany(groupH, delegate(IGrouping<int, Record> g) { return g; });
});

return Enumerable.SelectMany(groupT, delegate(IEnumerable<Record> g) { return g; });

}

You can either replace the ArrayList with a List<T>[^], or use the Cast[^] or OfType[^] methods to convert it to an IEnumerable<T>.

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

arnold_w

I get the following compiler error on all lines that contain the word Enumerable: The type arguments for method 'System.Linq.Enumerable.GroupBy(System.Collections.Generic.IEnumerable, System.Func)' cannot be inferred from the usage. Try specifying the type arguments explicitly. Does anybody know how I can correct this?

Richard Deeming

That's annoying. It sounds like C# 2.0 can't infer the generic type parameters properly. You might need to specify them explicitly:

public static IEnumerable<Record> SortRecords(IEnumerable<Record> source)
{
IEnumerable<IEnumerable<Record>> groupT = Enumerable.GroupBy<Record, int, IEnumerable<Record>>(source,
delegate(Record r) { return r.T; },
delegate(int key, IEnumerable<Record> items)
{
IEnumerable<IGrouping<int, Record>> groupH = Enumerable.GroupBy<Record, int>(items, delegate(Record r) { return r.H; });
return Enumerable.SelectMany<IEnumerable<Record>, Record>(groupH, delegate(IEnumerable<Record> g) { return g; });
});

return Enumerable.SelectMany<IEnumerable<Record>, Record>(groupT, delegate(IEnumerable<Record> g) { return g; });

}

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

Alan N

Let's do this the old way! Sorting on multiple keys with a comparer method is straightforward (and easy to understand?). It is just a nested set of comparisons, compare the first key, if equal compare the second key, etc. For example let's say we have a list of strings and we want a custom sort. 1) by string length 2) alphabetically within each group of equal length The comparer method is

private static Int32 SortByLengthThenAlpha(String x, String y) {
// 1st sort
Int32 result = x.Length.CompareTo(y.Length);
// result will be < 0, 0, > 0

if (result == 0) {
// 2nd Sort, standard string sort
result = x.CompareTo(y);

// and so on if more is needed
// if (result==0) {
// }
//

}
return result;
}

With an array of strings we can perform the sort with

Array.Sort(strings, SortByLengthThenAlpha);

Original Order

Reddish
Yellowish
Redder
Greenish
Red
Orange
Yellow
Orangy
Green

Sorted

Red
Green
Orange
Orangy
Redder
Yellow
Reddish
Greenish
Yellowish

Hope that helps explain the general idea. In your case the keys are the numeric values of T, H and L. Alan.

arnold_w

I think my example data was not so good, the following is probably better: Unsorted: "City" "Florida" "Miami" "Animal" "Land" "Dog" "Animal" "Land" "Rabbit" "Food" "Dessert" "Chocolate Mousse" "Food" "Dinner" "Hamburger" "Animal" "Water" "Fish" "Animal" "Land" "Cat" "Food" "Dessert" "Cake" "Animal" "Air" "Bird" "Food" "Dessert" "Ice Cream" "Food" "Dinner" "Steak" "Animal" "Water" "Sea Lion" "City" "Texas" "Austin" "Food" "Breakfast" "Cereal" "Food" "Breakfast" "Pancakes" "City" "Florida" "Tampa" "Animal" "Air" "Fly" "City" "California" "San Francisco" "Food" "Breakfast" "Bacon and Eggs" "City" "Texas" "Dallas" "City" "Texas" "Houston" "City" "California" "Los Angeles" "Animal" "Water" "Dolphin" "Animal" "Air" "Bee" "City" "Florida" "Orlando" "City" "California" "San Diego" "Food" "Dinner" "Lasagna" Sorted: "City" "Florida" "Miami" "City" "Florida" "Tampa" "City" "Florida" "Orlando" "City" "Texas" "Austin" "City" "Texas" "Dallas" "City" "Texas" "Houston" "City" "California" "San Francisco" "City" "California" "Los Angeles" "City" "California" "San Diego" "Animal" "Land" "Dog" "Animal" "Land" "Rabbit" "Animal" "Land" "Cat" "Animal" "Water" "Fish" "Animal" "Water" "Sea Lion" "Animal" "Water" "Dolphin" "Animal" "Air" "Bird" "Animal" "Air" "Fly" "Animal" "Air" "Bee" "Food" "Dessert" "Chocolate Mousse" "Food" "Dessert" "Cake" "Food" "Dessert" "Ice Cream" "Food" "Dinner" "Hamburger" "Food" "Dinner" "Steak" "Food" "Dinner" "Lasagna" "Food" "Breakfast" "Cereal" "Food" "Breakfast" "Bacon and Eggs" "Food" "Breakfast" "Pancakes" How would I then use your code to sort it?

Alan N

The problem you have is that the desired arrangement within the 3 columns has no discernable order. You are grouping terms, City, California, Water, Breakfast etc, but the order of the groups seems completely random. For example why is the order of the states Florida, Texas, California? There is nothing about the strings which would suggest that order so there must be some other factor which is not in the data that you have shown. Alan.

arnold_w

First, pretend only column 1 (tab page string) and column 2 (groupbox string) are present and then simply remove all duplicate rows. This is the sorted order for columns 1 and 2. Now, insert column 3 items in the groupbox where they belong and preserve the unsorted order within each groupbox.