C# Sort List Based on Another List

Question

I have a class that has multiple List<> contained within it. Its basically a table stored with each column as a List<>. Each column does not contain the same type. Each list is also the same length (has the same number of elements).

For example:

I have 3 List<> objects; one List, two List, and three List.

//Not syntactically correct
List<DateTime> one = new List...{4/12/2010, 4/9/2006, 4/13/2008};
List<double> two = new List...{24.5, 56.2, 47.4};
List<string> three = new List...{"B", "K", "Z"};

I want to be able to sort list one from oldest to newest: one = {4/9/2006, 4/13/2008, 4/12/2010};

So to do this I moved element 0 to the end.

I then want to sort list two and three the same way; moving the first to the last.

So when I sort one list, I want the data in the corresponding index in the other lists to also change in accordance with how the one list is sorted.

I'm guessing I have to overload IComparer somehow, but I feel like there's a shortcut I haven't realized.

Solution 1

I've handled this design in the past by keeping or creating a separate index list. You first sort the index list, and then use it to sort (or just access) the other lists. You can do this by creating a custom IComparer for the index list. What you do inside that IComparer is to compare based on indexes into the key list. In other words, you are sorting the index list indirectly. Something like:

// This is the compare function for the separate *index* list.
int Compare (object x, object y)
{
  KeyList[(int) x].CompareTo(KeyList[(int) y])
}

So you are sorting the index list based on the values in the key list. Then you can use that sorted key list to re-order the other lists. If this is unclear, I'll try to add a more complete example when I get in a situation to post one.

Solution 2

Here's a way to do it using LINQ and projections. The first query generates an array with the original indexes reordered by the datetime values; in your example, the newOrdering array would have members:

{ 4/9/2006, 1 }, { 4/13/2008, 2 }, { 4/12/2010, 0 }

The second set of statements generate new lists by picking items using the reordered indexes (in other words, items 1, 2, and 0, in that order).

var newOrdering = one
    .Select((dateTime, index) => new { dateTime, index })
    .OrderBy(item => item.dateTime)
    .ToArray();

// now, order each list
one = newOrdering.Select(item => one[item.index]).ToList();
two = newOrdering.Select(item => two[item.index]).ToList();
three = newOrdering.Select(item => three[item.index]).ToList();

Solution 3

I am sorry to say, but this feels like a bad design. Especially because List<T> does not guarantee element order before you have called one of the sorting operations (so you have a problem when inserting):

From MSDN:

The List is not guaranteed to be sorted. You must sort the List before performing operations (such as BinarySearch) that require the List to be sorted.

In many cases you won't run into trouble based on this, but you might, and if you do, it could be a very hard bug to track down. For example, I think the current framework implementation of List<T> maintains insert order until sort is called, but it could change in the future.

I would seriously consider refactoring to use another data structure. If you still want to implement sorting based on this data structure, I would create a temporary object (maybe using an anonymous type), sort this, and re-create the lists (see this excellent answer for an explanation of how).

Solution 4

I wrote a sort algorithm that does this for Nito.LINQ (not yet released). It uses a simple-minded QuickSort to sort the lists, and keeps any number of related lists in sync. Source code starts here, in the IList<T>.Sort extension method.

Alternatively, if copying the data isn't a huge concern, you could project it into a LINQ query using the Zip operator (requires .NET 4.0 or Rx), order it, and then pull each result out:

List<DateTime> one = ...;
List<double> two = ...;
List<string> three = ...;
var combined = one.Zip(two, (first, second) => new { first, second })
    .Zip(three, (pair, third) => new { pair.first, pair.second, third });
var ordered = combined.OrderBy(x => x.first);
var orderedOne = ordered.Select(x => x.first);
var orderedTwo = ordered.Select(x => x.second);
var orderedThree = ordered.Select(x => x.third);

Naturally, the best solution is to not separate related data in the first place.

Solution 5

First you should create a Data object to hold everything.

private class Data
{
    public DateTime DateTime { get; set; }
    public int Int32 { get; set; }
    public string String { get; set; }
}

Then you can sort like this.

var l = new List<Data>();
l.Sort(
    (a, b) =>
    {
        var r = a.DateTime.CompareTo(b);
        if (r == 0)
        {
            r = a.Int32.CompareTo(b);
            if (r == 0)
            {
                r = a.String.CompareTo(b);
            }
        }
        return r;
    }
);

View more solutions

Comments

[Admin]

So I iterate through the entirety of each list and create a Data struct from the data. Then I sort the data, then I put it back into the lists. This makes sense, but it doesn't seem that efficient. It will at least work and thats better than what I currently have. Thanks. Edit: I don't neccesarily know that there are 3 items so I can't use a struct. A list could probably work but would I have to worry about casting on the big sort?

[ChaosPandion]

@John - Do you receive these lists from an uncontrollable source?

[Admin]

Yeah, the List<> objects I recieve cannot be changed; they can be sorted in place though.

[Stephen Cleary]

+1. This is an excellent approach. I have exactly this kind of "indirect list" in my personal library; it's useful for many things. Sample code here.

[TechNeilogy]

I agree there are better designs. The main situations in which I've run into this in the past is where I didn't have ownership of the original arrays and they were too big to make separate copies. If you have ownership, by all means re-factor this into an IComparable class or structure with all the data.

[Admin]

I like this solution, but is it efficient? I don't know that much about prjection performance;

[Admin]

I can't really change this but here's the application. Basically the List<> objects contain data and that data is passed to math functions. The math functions then pass the result back and are appended to the table class. Would it be better to store this stuff row-wise and project out the columns using LINQ? That makes the insert much more complicated however.

[driis]

Yes, I certainly think it would be better to store row-wise. I don't see how inserts would be more complicated by that; but then again, I don't know about the entire application and your constraints.

[Ben M]

Only one way to find out - :-)

[Mauro Ganswer]

As far as I know List<T> does not guarantee element to be be sorted but it does guarantee element order according to the insertion order (see here for instance), hence there is not a strictly need for refactoring.

[Olivier MATROT]

Here is the updated source code link.