Sorting a list of objects based on another

Question

public class Product
{
    public string Code { get; private set; }

    public Product(string code)
    {
        Code = code;
    }
}

List<Product> sourceProductsOrder = 
              new List<Product>() { new Product("BBB"), new Product("QQQ"), 
                                    new Product("FFF"), new Product("HHH"),
                                    new Product("PPP"), new Product("ZZZ")};

List<Product> products = 
              new List<Product>() { new Product("ZZZ"), new Product("BBB"),
                                    new Product("HHH")};

I have two product lists and I want to reorder the second one with the same order as the first. How can I reorder the products list so that the result would be : "BBB", "HHH", "ZZZ"?

EDIT: Changed Code property to public as @juharr mentioned

So the two lists have a separate Product("BBB") object, or is it the same object shared between the two lists? — JLRishe
– JLRishe, Commented Jan 5, 2015 at 16:42
@YoupTube I can see what the example code shows. I'm asking what's actually happening in OP's program. — JLRishe
– JLRishe, Commented Jan 5, 2015 at 16:43
@HélderGonçalves If they are different objects you either need to make Code public, or override the Equals (and GetHashCode) method of Product to compare the Code value. — juharr
– juharr, Commented Jan 5, 2015 at 16:50
FYI: Code is currently a public field, not a property, which is generally considered a bad practice. You can make it an auto property like this public string Code { get; private set; }. This also makes the object immutable which you may or may not find desirable. — juharr
– juharr, Commented Jan 5, 2015 at 17:00

Corey Adler · Accepted Answer · 2015-01-05 16:46:48Z

3

You would use IndexOf:

var sourceCodes = sourceProductsOrder.Select(s => s.Code).ToList();
products = products.OrderBy(p => sourceCodes.IndexOf(p.Code));

The only catch to this is if the second list has something not in the first list those will go to the beginning of the second list.

MSDN post on IndexOf can be found here.

answered Jan 5, 2015 at 16:46

Corey Adler

16.2k18 gold badges70 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

WeSt Over a year ago

sourceProductsOrder.Select(s => s.Code).ToList().IndexOf(p) will always yield 0 (asuming there is only one product of each description), or am I mistaken?

Corey Adler Over a year ago

Thanks for that. Forgot to say p.Code.

WeSt · Accepted Answer · 2015-01-05 16:46:37Z

2

You could try something like this

products.OrderBy(p => sourceProductsOrder.IndexOf(p))

if it is the same Product object. Otherwise, you could try something like:

products.OrderBy(p => GetIndex(sourceProductsOrder, p))

and write a small GetIndex helper method. Or create a Index() extension method for List<>, which would yield

products.OrderBy(p => sourceProductsOrder.Index(p))

The GetIndex method is rather simple so I omit it here.

(I have no PC to run the code so please excuse small errors)

answered Jan 5, 2015 at 16:46

WeSt

2,7085 gold badges27 silver badges43 bronze badges

Comments

JLRishe · Accepted Answer · 2015-01-05 17:19:25Z

2

Here is an efficient way to do this:

var lookup = sourceProductsOrder.Select((p, i) => new { p.Code, i })
                                .ToDictionary(x => x.Code, x => x.i);

products = products.OrderBy(p => lookup[p.Code]).ToList();

This should have a running time complexity of O(N log N), whereas an approach using IndexOf() would be O(N²).

This assumes the following:

there are no duplicate product codes in sourceProductsOrder
sourceProductsOrder contains all of the product codes in products
you make the Code field/property non-private

If needed, you can create a safeguard against the first bullet by replacing the first statement with this:

var lookup = sourceProductsOrder.GroupBy(p => p.Code)
                                .Select((g, i) => new { g.Key, i })
                                .ToDictionary(x => x.Key, x => x.i);

You can account for the second bullet by replacing the second statement with this:

products = products.OrderBy(p => 
            lookup.ContainsKey(p.Code) ?  lookup[p.Code] : Int32.MaxValue).ToList();

And you can use both if you need to. These will slow down the algorithm a bit, but it should continue to have an O(N log N) running time even with these alterations.

edited Jan 5, 2015 at 17:19

answered Jan 5, 2015 at 16:53

JLRishe

102k19 gold badges138 silver badges171 bronze badges

3 Comments

Corey Adler Over a year ago

Wouldn't there be an exception if the item from products wasn't in sourceProductsOwner here?

JLRishe Over a year ago

@IronMan84 Indeed there would be. I was in the midst of adding something to account for that.

JLRishe Over a year ago

@YoupTube It's not a copy. We arrived at similar solutions independently. And now my answer contains information that his doesn't.

wilkesybear · Accepted Answer · 2015-01-05 16:47:21Z

0

I would implement a compare function that does a lookup of the order from sourceProductsOrder using a hash table. The lookup table would look like

(key) : (value)
"BBB" : 1
"QQQ" : 2
"FFF" : 3
"HHH" : 4
"PPP" : 5
"ZZZ" : 6

Your compare could then lookup the order of the two elements and do a simple < (pseudo code):

int compareFunction(Product a, Product b){ 
    return lookupTable[a] < lookupTable[b]
}

Building the hash table would be linear and doing the sort would generally be nlogn

answered Jan 5, 2015 at 16:47

wilkesybear

5383 silver badges9 bronze badges

Comments

Youp Bernoulli · Accepted Answer · 2015-01-05 17:04:33Z

0

Easy come easy go:

IEnumerable<Product> result = 

products.OrderBy(p => sourceProductsOrder.IndexOf(sourceProductsOrder.FirstOrDefault(p2 => p2.Code == p.Code)));

This will provide the desired result. Objects with ProductCodes not available in the source list will be placed at the beginning of the resultset. This will perform just fine for a couple of hundred of items I suppose.

If you have to deal with thousands of objects than an answer like @Jon's will likely perform better. There you first create a kind of lookup value / score for each item and then use that for sorting / ordering.

The approach I described is O(n2).

answered Jan 5, 2015 at 17:04

Youp Bernoulli

5,7127 gold badges45 silver badges63 bronze badges

Collectives™ on Stack Overflow

Sorting a list of objects based on another

5 Answers 5

2 Comments

Comments

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related