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.

Answer 1

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;
    }
);

Answer 2

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.

Answer 3

Using generic arrays, this can get a bit cumbersome.

One alternative is using the Array.Sort() method that takes an array of keys and an array of values to sort. It first sorts the key array into ascending order and makes sure the array of values is reorganized to match this sort order.

If you're willing to incur the cost of converting your List<T>s to arrays (and then back), you could take advantage of this method.

Alternatively, you could use LINQ to combine the values from multiple arrays into a single anonymous type using Zip(), sort the list of anonymous types using the key field, and then split that apart into separate arrays.

If you want to do this in-place, you would have to write a custom comparer and create a separate index array to maintain the new ordering of items.

Answer 4

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).

Answer 5

I hope this could help :

one = one.Sort(delegate(DateTime d1, DateTime d2)
{
    return Convert.ToDateTime(d2).CompareTo(Convert.ToDateTime(d1));
});

Answer 6

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.

Answer 7

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();